Can Place Flowers

Difficulty: Easy | Acceptance: 29.10% | Paid: No Topics: Array, Greedy

Suppose 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.

• Examples
• Constraints
• Greedy Single Pass (In-place)
• Greedy Single Pass (No Modification)
• Counting Consecutive Zeros

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 * 10⁴
flowerbed[i] is 0 or 1.
There are no two adjacent flowers in flowerbed.
0 <= n <= flowerbed.length

Greedy Single Pass (In-place)

Intuition We can iterate through the flowerbed and greedily plant a flower whenever we find an empty spot (0) that has empty neighbors (or is at the boundary). Modifying the array in place helps us keep track of newly planted flowers easily.

Steps

• Iterate through the flowerbed array.
• For each plot that is 0, check if the previous and next plots are also 0 (or out of bounds).
• If valid, plant a flower by setting the current plot to 1 and decrement n.
• If n reaches 0, return true immediately.
• If the loop finishes, return whether n is less than or equal to 0.

from typing import List

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        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

Complexity

• Time: O(n) — We traverse the array once.
• Space: O(1) — We only use a few extra variables.
• Notes: Modifies the input array, which might not be desired in all contexts.

Greedy Single Pass (No Modification)

Intuition Similar to the in-place approach, but instead of modifying the array, we use a variable to track if the previous position was planted. This preserves the original input.

Steps

• Initialize prev to 0 (indicating the position before the start is empty).
• Iterate through the array.
• If the current plot is 0, check if prev is 0 and the next plot is 0 (or we are at the end).
• If valid, increment the count and set prev to 1 (indicating we planted here).
• Otherwise, set prev to the current plot’s value.
• If the current plot is 1, set prev to 1.
• Return whether the count is greater than or equal to n.

from typing import List

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        count = 0
        length = len(flowerbed)
        prev = 0
        for i in range(length):
            if flowerbed[i] == 0:
                if prev == 0 and (i == length - 1 or flowerbed[i+1] == 0):
                    count += 1
                    prev = 1
                else:
                    prev = 0
            else:
                prev = 1
        return count >= n

Complexity

• Time: O(n) — Single pass through the array.
• Space: O(1) — Constant extra space.
• Notes: Does not modify the input array.

Counting Consecutive Zeros

Intuition We can calculate the maximum number of flowers that can fit in segments of consecutive zeros. For a segment of k zeros bounded by 1s, we can plant (k-1)/2 flowers. For segments at the edges, we can plant k/2 flowers.

Steps

• Initialize count to 0 and prev to -1 (index of the last seen 1).
• Iterate through the array to find indices of 1s.
• For each 1 found at index i, calculate the number of zeros between prev and i.
• If prev is -1, it’s a leading edge segment. Add i / 2 to count.
• Otherwise, it’s a middle segment. Add (i - prev - 2) / 2 to count.
• Update prev to i.
• After the loop, handle the trailing edge segment (from prev to end of array).
• Return count >= n.

from typing import List

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        count = 0
        m = len(flowerbed)
        prev = -1
        for i in range(m):
            if flowerbed[i] == 1:
                if prev == -1:
                    count += i // 2
                else:
                    count += (i - prev - 2) // 2
                prev = i
        # Handle trailing zeros
        if prev == -1:
            count += (m + 1) // 2
        else:
            count += (m - prev - 1) // 2
        return count >= n

Complexity

• Time: O(n) — One pass to find 1s.
• Space: O(1) — Only a few integer variables used.
• Notes: Slightly more complex logic to handle edge cases, but very efficient.