Problem Description

The "Can Place Flowers" problem asks you to determine if it is possible to plant a given number (n) of new flowers in a flowerbed, represented by an array, without violating the rule that no two flowers can be planted in adjacent plots.

The flowerbed is represented as an array of integers (flowerbed), where 0 means the plot is empty, and 1 means the plot already has a flower. You must return true if you can plant n new flowers in the flowerbed without breaking the rule, and false otherwise. You cannot plant flowers in plots already containing a flower, and you must not plant flowers in adjacent plots.

• The input flowerbed is a list of 0s and 1s.
• The input n is a non-negative integer.
• Only one valid solution is needed.
• You cannot reuse or overwrite existing flowers.

Thought Process

At first glance, the problem seems to invite a brute-force approach: for each plot in the flowerbed, check if we can plant a flower there without violating the adjacency rule. But that could be inefficient and may involve checking lots of unnecessary combinations.

We notice that the only thing that matters for any position is whether its immediate neighbors are empty. So, if both the left and right plots (if they exist) are 0, and the current plot is 0, we can plant a flower there. After planting, we must "skip" the next plot since adjacent planting isn't allowed.

Instead of generating all possible arrangements, we can simply scan the array once, greedily planting flowers wherever possible, and counting until we reach n. If we do, we return true; otherwise, false.

Solution Approach

Let's break down the steps to solve this problem efficiently:

1. Iterate through the flowerbed:
   • Go through each plot (index i) in the array.
2. Check if planting is possible:
   • For each plot, check if it is empty (flowerbed[i] == 0).
   • Also check the left neighbor (i == 0 or flowerbed[i-1] == 0).
   • And the right neighbor (i == len(flowerbed) - 1 or flowerbed[i+1] == 0).
3. Plant the flower if possible:
   • If all the above are true, set flowerbed[i] = 1 (plant a flower).
   • Increment the count of newly planted flowers.
4. Early exit:
   • If the count reaches n, return true immediately.
5. Return result:
   • If the loop finishes and we haven't reached n, return false.

This approach is efficient because it only checks the minimum required plots and modifies the array in place for simplicity.

Example Walkthrough

Let's use the example: flowerbed = [1,0,0,0,1], n = 1.

1. Start at index 0: flowerbed[0] == 1 (already planted), skip.
2. Index 1: flowerbed[1] == 0, left neighbor is 1 (flowerbed[0]), so can't plant here.
3. Index 2: flowerbed[2] == 0, left is 0 (flowerbed[1]), right is 0 (flowerbed[3]), so we can plant here. Set flowerbed[2] = 1, increment count to 1.
4. Since count == n, return true.

If instead n = 2, we would continue but find no more valid spots, so the answer would be false.

Time and Space Complexity

• Brute-force approach: Would try all possible combinations, which could be exponential in the number of empty plots (O(2^m), where m is the number of zeros).
• Optimized greedy approach (our solution):
  • Time Complexity: O(N), where N is the length of the flowerbed. We scan each plot at most once.
  • Space Complexity: O(1) if we modify the array in place; O(N) if we make a copy.

Summary

The "Can Place Flowers" problem is elegantly solved with a greedy, single-pass approach. By only checking the immediate neighbors for each empty plot, we avoid unnecessary combinations and reach an answer efficiently. The key insight is that local decisions (whether a spot and its neighbors are empty) are sufficient to find a global solution, making the problem approachable even for beginners.

Code Implementation

class Solution:
    def canPlaceFlowers(self, flowerbed, n):
        count = 0
        length = len(flowerbed)
        for i in range(length):
            if flowerbed[i] == 0:
                empty_left = (i == 0) or (flowerbed[i - 1] == 0)
                empty_right = (i == length - 1) or (flowerbed[i + 1] == 0)
                if empty_left and empty_right:
                    flowerbed[i] = 1
                    count += 1
                    if count >= n:
                        return True
        return count >= n
      

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int count = 0;
        int length = flowerbed.size();
        for (int i = 0; i < length; ++i) {
            if (flowerbed[i] == 0) {
                bool empty_left = (i == 0) || (flowerbed[i - 1] == 0);
                bool empty_right = (i == length - 1) || (flowerbed[i + 1] == 0);
                if (empty_left && empty_right) {
                    flowerbed[i] = 1;
                    count++;
                    if (count >= n) return true;
                }
            }
        }
        return count >= n;
    }
};
      

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        int length = flowerbed.length;
        for (int i = 0; i < length; i++) {
            if (flowerbed[i] == 0) {
                boolean emptyLeft = (i == 0) || (flowerbed[i - 1] == 0);
                boolean emptyRight = (i == length - 1) || (flowerbed[i + 1] == 0);
                if (emptyLeft && emptyRight) {
                    flowerbed[i] = 1;
                    count++;
                    if (count >= n) return true;
                }
            }
        }
        return count >= n;
    }
}
      

var canPlaceFlowers = function(flowerbed, n) {
    let count = 0;
    let length = flowerbed.length;
    for (let i = 0; i < length; i++) {
        if (flowerbed[i] === 0) {
            let emptyLeft = (i === 0) || (flowerbed[i - 1] === 0);
            let emptyRight = (i === length - 1) || (flowerbed[i + 1] === 0);
            if (emptyLeft && emptyRight) {
                flowerbed[i] = 1;
                count++;
                if (count >= n) return true;
            }
        }
    }
    return count >= n;
};