605. Can Place Flowers

EasyView on LeetCode

Array Greedy

Time: O(n)

Space: O(1)

Intuition

Greedily plant flowers: if position i and its neighbors are all 0, plant at i (set flowerbed[i]=1) and continue.

Algorithm

1Iterate through flowerbed.
2At each index i, check flowerbed[i]==0 and (i==0 or flowerbed[i-1]==0) and (i==n-1 or flowerbed[i+1]==0).
3If true, plant: set flowerbed[i]=1, count++.
4Return count >= n.

Common Pitfalls

•Modifying the array in-place (marking 1) prevents us from planting at adjacent positions without extra checks.

605.cs

// Approach: Greedy single pass — plant a flower whenever the current cell
// and both neighbors are empty; modify the array in-place.
// Time: O(n) Space: O(1)

public class Solution
{
    public bool CanPlaceFlowers(int[] flowerbed, int n)
    {
        if (n == 0)
            return true;

        for (int i = 0; i < flowerbed.Length; i++)
        {
            if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0)
            && (i == flowerbed.Length - 1 || flowerbed[i + 1] == 0))
            {
                flowerbed[i] = 1;
                if (--n == 0)
                    return true;
            }
        }

        return false;
    }
}

Was this solution helpful?