The Flower Planting Problem#

Imagine you have a long flowerbed, some plots are planted with flowers, while others are not. However, flowers cannot be planted on adjacent plots, as they will compete for water and both will die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 represents no flower planted, and 1 represents a planted flower), and a number n. Can you plant n flowers without breaking the planting rules? If yes, return True, otherwise return False.

Example#

Solution#

/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function(flowerbed, n) {
    let count = 0;
    flowerbed.forEach((v, i) => {
        if (flowerbed[i - 1] !== 1 && flowerbed[i] !== 1 && flowerbed[i + 1] !== 1) {
            flowerbed[i] = 1;
            count += 1;
        }
    });
    return count >= n;
};

Idea#

Just need to iterate through the flowerbed. In fact, except for the beginning and end, as long as there are 3 consecutive 0 items, a position suitable for planting flowers can be determined. This problem can be further simplified to iterating through all the flowerbeds, planting a flower at a position where neither the left nor right is planted. The data structure is not remembered, just brute force. First, define a count variable, then iterate through the flowerbed, checking whether the left and right of the current value are planted with flowers. There's no need to pay much attention to array boundary problems here, as in JavaScript, accessing an undefined index in an array returns undefined, which is also not equal to 1. If it's determined that neither the left nor the right is planted, plant a flower at that position and increase the count. Then, compare the count of flowers planted with n and return the result.

Daily Problem#

Reference#