605. Can Place Flowers - Explanation

Description

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.

You are 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 <= 20,000
flowerbed[i] is 0 or 1.
There are no two adjacent flowers in flowerbed.
0 <= n <= flowerbed.length

Topics

Array Greedy

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Arrays - Traversing arrays and checking adjacent elements
Greedy Algorithms - Making locally optimal choices (planting when possible) to achieve the best result
Boundary Handling - Managing edge cases at the start and end of arrays

1. Iteration - I

Intuition

A flower can be planted at position i only if positions i-1, i, and i+1 are all empty. To handle edge cases at the boundaries, we pad the flowerbed with zeros at both ends. This way, we can apply the same rule uniformly across all positions without special boundary checks.

Algorithm

Create a new array with a 0 prepended and appended to the original flowerbed.
Iterate through the padded array from index 1 to length-2 (the original positions).
For each position, check if the current cell and both neighbors are empty (all zeros).
If so, plant a flower by setting the current cell to 1, and decrement n.
After processing all positions, return true if n is 0 or less (we placed enough flowers).

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        f = [0] + flowerbed + [0]

        for i in range(1, len(f) - 1):
            if f[i - 1] == 0 and f[i] == 0 and f[i + 1] == 0:
                f[i] = 1
                n -= 1

        return n <= 0

public class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int[] f = new int[flowerbed.length + 2];
        for (int i = 0; i < flowerbed.length; i++) {
            f[i + 1] = flowerbed[i];
        }

        for (int i = 1; i < f.length - 1; i++) {
            if (f[i - 1] == 0 && f[i] == 0 && f[i + 1] == 0) {
                f[i] = 1;
                n--;
            }
        }
        return n <= 0;
    }
}

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        vector<int> f(flowerbed.size() + 2, 0);
        for (int i = 0; i < flowerbed.size(); i++) {
            f[i + 1] = flowerbed[i];
        }

        for (int i = 1; i < f.size() - 1; i++) {
            if (f[i - 1] == 0 && f[i] == 0 && f[i + 1] == 0) {
                f[i] = 1;
                n--;
            }
        }
        return n <= 0;
    }
};

class Solution {
    /**
     * @param {number[]} flowerbed
     * @param {number} n
     * @return {boolean}
     */
    canPlaceFlowers(flowerbed, n) {
        const f = [0, ...flowerbed, 0];

        for (let i = 1; i < f.length - 1; i++) {
            if (f[i - 1] === 0 && f[i] === 0 && f[i + 1] === 0) {
                f[i] = 1;
                n--;
            }
        }
        return n <= 0;
    }
}

public class Solution {
    public bool CanPlaceFlowers(int[] flowerbed, int n) {
        int[] f = new int[flowerbed.Length + 2];
        for (int i = 0; i < flowerbed.Length; i++) {
            f[i + 1] = flowerbed[i];
        }

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

        return n <= 0;
    }
}

class Solution {
    fun canPlaceFlowers(flowerbed: IntArray, n: Int): Boolean {
        var n = n
        val f = IntArray(flowerbed.size + 2)
        for (i in flowerbed.indices) {
            f[i + 1] = flowerbed[i]
        }

        for (i in 1 until f.size - 1) {
            if (f[i - 1] == 0 && f[i] == 0 && f[i + 1] == 0) {
                f[i] = 1
                n--
            }
        }

        return n <= 0
    }
}

class Solution {
    func canPlaceFlowers(_ flowerbed: [Int], _ n: Int) -> Bool {
        var n = n
        var f = [0] + flowerbed + [0]

        for i in 1..<(f.count - 1) {
            if f[i - 1] == 0 && f[i] == 0 && f[i + 1] == 0 {
                f[i] = 1
                n -= 1
            }
        }

        return n <= 0
    }
}

impl Solution {
    pub fn can_place_flowers(flowerbed: Vec<i32>, n: i32) -> bool {
        let mut n = n;
        let mut f = vec![0];
        f.extend_from_slice(&flowerbed);
        f.push(0);

        for i in 1..f.len() - 1 {
            if f[i - 1] == 0 && f[i] == 0 && f[i + 1] == 0 {
                f[i] = 1;
                n -= 1;
            }
        }

        n <= 0
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Iteration - II

Intuition

Instead of checking each position individually, we can count consecutive empty plots between flowers. For a sequence of k empty plots between two flowers, we can plant (k-1)/2 flowers. At the beginning and end of the flowerbed, the formula differs slightly since there is no blocking flower on one side: we can plant k/2 flowers at the edges.

Algorithm

Initialize an empty plot counter. If the first cell is empty, start the counter at 1 (treating the left boundary as open).
Iterate through each cell in the flowerbed.
When encountering a flower (1), calculate how many new flowers can fit in the empty sequence before it using (empty-1)/2, then reset the counter.
When encountering an empty cell (0), increment the counter.
After the loop, handle the trailing empty sequence using empty/2 (right boundary is open).
Return true if we placed at least n flowers.

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        empty = 0 if flowerbed[0] else 1

        for f in flowerbed:
            if f:
                n -= int((empty - 1) / 2)
                empty = 0
            else:
                empty += 1

        n -= empty // 2
        return n <= 0

public class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int empty = flowerbed[0] == 0 ? 1 : 0;

        for (int f : flowerbed) {
            if (f == 1) {
                n -= (empty - 1) / 2;
                empty = 0;
            } else {
                empty++;
            }
        }

        n -= empty / 2;
        return n <= 0;
    }
}

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int empty = flowerbed[0] == 0 ? 1 : 0;

        for (int f : flowerbed) {
            if (f == 1) {
                n -= (empty - 1) / 2;
                empty = 0;
            } else {
                empty++;
            }
        }

        n -= empty / 2;
        return n <= 0;
    }
};

class Solution {
    /**
     * @param {number[]} flowerbed
     * @param {number} n
     * @return {boolean}
     */
    canPlaceFlowers(flowerbed, n) {
        let empty = flowerbed[0] === 0 ? 1 : 0;

        for (let f of flowerbed) {
            if (f === 1) {
                n -= Math.floor(Math.max(0, empty - 1) / 2);
                empty = 0;
            } else {
                empty++;
            }
        }

        n -= Math.floor(empty / 2);
        return n <= 0;
    }
}

public class Solution {
    public bool CanPlaceFlowers(int[] flowerbed, int n) {
        int empty = flowerbed[0] == 0 ? 1 : 0;

        foreach (int f in flowerbed) {
            if (f == 1) {
                n -= (empty - 1) / 2;
                empty = 0;
            } else {
                empty++;
            }
        }

        n -= empty / 2;
        return n <= 0;
    }
}

func canPlaceFlowers(flowerbed []int, n int) bool {
    empty := 0
    if flowerbed[0] == 0 {
        empty = 1
    }

    for _, f := range flowerbed {
        if f == 1 {
            n -= (empty - 1) / 2
            empty = 0
        } else {
            empty++
        }
    }

    n -= empty / 2
    return n <= 0
}

class Solution {
    fun canPlaceFlowers(flowerbed: IntArray, n: Int): Boolean {
        var n = n
        var empty = if (flowerbed[0] == 0) 1 else 0

        for (f in flowerbed) {
            if (f == 1) {
                n -= (empty - 1) / 2
                empty = 0
            } else {
                empty++
            }
        }

        n -= empty / 2
        return n <= 0
    }
}

class Solution {
    func canPlaceFlowers(_ flowerbed: [Int], _ n: Int) -> Bool {
        var n = n
        var empty = flowerbed[0] == 0 ? 1 : 0

        for f in flowerbed {
            if f == 1 {
                n -= (empty - 1) / 2
                empty = 0
            } else {
                empty += 1
            }
        }

        n -= empty / 2
        return n <= 0
    }
}

impl Solution {
    pub fn can_place_flowers(flowerbed: Vec<i32>, n: i32) -> bool {
        let mut n = n;
        let mut empty = if flowerbed[0] == 0 { 1 } else { 0 };

        for &f in &flowerbed {
            if f == 1 {
                n -= (empty - 1) / 2;
                empty = 0;
            } else {
                empty += 1;
            }
        }

        n -= empty / 2;
        n <= 0
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Forgetting to Mark Planted Flowers

After deciding to plant a flower at position i, you must update the flowerbed to reflect the new flower. Otherwise, you may count overlapping positions as valid.

# Wrong: not updating the flowerbed after planting
if f[i-1] == 0 and f[i] == 0 and f[i+1] == 0:
    n -= 1  # Missing: f[i] = 1

Off-by-One Errors at Boundaries

When not padding the array, forgetting to handle the first and last positions specially leads to index-out-of-bounds errors or incorrect neighbor checks.