{x}
blog image

Can Place Flowers

You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.

Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.

 

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

Solution Explanation: Can Place Flowers

This problem asks whether we can plant n new flowers in a flowerbed represented by a 0-1 array (flowerbed), where 0 means empty and 1 means occupied. The constraint is that flowers cannot be planted in adjacent plots.

The optimal approach is a greedy algorithm. We iterate through the flowerbed array and look for opportunities to plant flowers. A flower can be planted at index i if:

  1. flowerbed[i] is 0 (empty).
  2. flowerbed[i-1] is 0 (no flower to the left).
  3. flowerbed[i+1] is 0 (no flower to the right).

We handle edge cases (first and last plots) carefully. If we find such a spot, we plant a flower (flowerbed[i] = 1), decrement n (the number of flowers still needed), and continue.

After iterating through the whole array, if n is less than or equal to 0, it means we successfully planted enough flowers, and we return true. Otherwise, we return false.

Time and Space Complexity

  • Time Complexity: O(m), where m is the length of the flowerbed array. We iterate through the array at most once.
  • Space Complexity: O(1). We use a constant amount of extra space, regardless of the input size. In some implementations, we might add a small, constant number of elements to the array (padding with zeros), but this doesn't change the overall space complexity.

Code Implementations (with explanations)

Python3:

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        # Pad the flowerbed with zeros to simplify boundary checks
        flowerbed = [0] + flowerbed + [0] 
        for i in range(1, len(flowerbed) - 1):
            # Check if we can plant a flower at index i
            if flowerbed[i-1] == 0 and flowerbed[i] == 0 and flowerbed[i+1] == 0:
                flowerbed[i] = 1  # Plant the flower
                n -= 1            # Decrement the number of flowers needed
        return n <= 0  # Return True if we planted enough flowers

Java:

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int m = flowerbed.length;
        for (int i = 0; i < m; ++i) {
            int l = (i == 0) ? 0 : flowerbed[i - 1]; //Left neighbor (or 0 if at the beginning)
            int r = (i == m - 1) ? 0 : flowerbed[i + 1]; // Right neighbor (or 0 if at the end)
            if (l + flowerbed[i] + r == 0) { //Check for possibility to plant
                flowerbed[i] = 1;
                n--;
            }
        }
        return n <= 0;
    }
}

The other languages (C++, Go, TypeScript, Rust, PHP) follow similar logic, with minor syntax differences to handle array access and conditional checks. The core greedy algorithm remains the same across all implementations.