Can Place Flowers

Problem Statement

In this problem, we are given a flowerbed represented as an integer array, where each element can be either 0 or 1. A 0 indicates that the plot is empty and available for planting a flower, while a 1 indicates that the plot is already occupied by a flower. Given the constraints of the flowerbed where placing flowers in adjacent plots is not allowed (i.e., no two consecutive elements in the array can both be 1s), our goal is to determine if it is possible to add at least n more flowers into the flowerbed without violating this spacing rule.

Examples

Example 1

Input:

flowerbed = [1,0,0,0,1], n = 1

Output:

true

Example 2

Input:

flowerbed = [1,0,0,0,1], n = 2

Output:

false

Constraints

• 1 <= flowerbed.length <= 2 * 104
• flowerbed[i] is 0 or 1.
• There are no two adjacent flowers in flowerbed.
• 0 <= n <= flowerbed.length

Approach and Intuition

To solve this problem, one must traverse the flowerbed and figure out the potential slots where new flowers can be added while keeping the rule of not planting in adjacent plots in tact. Here's a step-by-step breakdown:

1. Initialize a counter: This counter will track the number of flowers that can potentially be planted.

2. Traverse the flowerbed: Iterate over the array elements.

   • Check surrounding plots: For each empty plot (0), check both its left and right neighbors.

   • Edge cases for boundaries:

     • If it's the first plot and it’s empty (flowerbed[0] == 0), check if the second plot is also empty or does not exist (in case the flowerbed has only one plot). If true, place a flower here and change value to 1.
     • If it’s the last plot and it's empty (flowerbed[n - 1] == 0), check the second last plot. If it's not planted (flowerbed[n - 2] == 0 or n < 2), plant a flower in the last plot.

   • For middle plots: If a plot is surrounded by empty plots or boundary conditions (flowerbed[i-1] == 0 && flowerbed[i+1] == 0), plant a flower there.

3. Increment the counter each time a flower is planted: Every time you determine that a flower can be planted in a slot without violating the no-adjacent rule, increase the counter.

4. Comparison with n: After evaluating the entire flowerbed, compare the counter with n. If the counter is at least n, return true; otherwise, return false.

Each evaluation involves looking at the current plot and its adjacent ones, which will ensure that the no-adjacent rule is adhered to throughout. This method provides an efficient way to maximize the number of new flowers in the given constraints.

Solutions

class Solution {
public:
    bool canPlant(vector<int>& garden, int n) {
        int planted = 0;
        for (int i = 0; i < garden.size(); i++) {
            if (garden[i] == 0) {
                bool leftSafe = (i == 0) || (garden[i - 1] == 0);
                bool rightSafe = (i == garden.size() - 1) || (garden[i + 1] == 0);
                    
                if (leftSafe && rightSafe) {
                    garden[i] = 1;
                    planted++;
                    if (planted >= n) {
                        return true;
                    }
                }
            }
        }
        return planted >= n;
    }
};