LeetCode 605 - Can Place Flowers

The problem gives us a binary array called flowerbed, where: - 0 represents an empty plot - 1 represents a plot that already contains a flower We are also given an integer n, which represents how many new flowers we want to plant.

leetcodeeasyarraygreedy

LeetCode Problem 605

Difficulty: 🟢 Easy
Topics: Array, Greedy

Solution

Problem Understanding

The problem gives us a binary array called flowerbed, where:

  • 0 represents an empty plot
  • 1 represents a plot that already contains a flower

We are also given an integer n, which represents how many new flowers we want to plant.

The key restriction is that flowers cannot be planted in adjacent plots. This means if a plot contains a flower, the plots immediately to its left and right cannot contain flowers.

The task is to determine whether it is possible to plant exactly n new flowers without breaking this adjacency rule. We do not need to return the modified flowerbed, only whether planting n flowers is possible.

In other words, we want to greedily find valid empty positions where flowers can be planted while ensuring no two flowers become adjacent.

The input size is constrained as follows:

  • 1 <= flowerbed.length <= 2 * 10^4
  • Each value is either 0 or 1
  • The flowerbed already satisfies the no-adjacent-flowers condition
  • 0 <= n <= flowerbed.length

These constraints tell us that the input can be fairly large, up to twenty thousand elements. Since this is an Easy problem and the array size is moderate, an O(n) solution is ideal and straightforward to implement.

There are several important edge cases to think about before designing a solution.

A flowerbed of length 1 is special. For example, [0] can accept one flower, while [1] cannot. Boundary positions are tricky because they have only one neighbor instead of two.

Another important case occurs at the beginning or end of the array. For example, [0,0,1] or [1,0,0] requires careful handling because one side is missing.

We also need to consider n = 0. In this case, the answer should always be true, since we do not need to plant anything.

Finally, a naive implementation may accidentally allow adjacent placements during iteration if it does not update the flowerbed correctly after planting.

Approaches

Brute Force Approach

A brute-force approach would try every possible planting combination and check whether at least n flowers can be placed without violating the adjacency rule.

For each empty position, we could recursively decide whether to place a flower or skip it, then verify whether the resulting arrangement remains valid. This guarantees correctness because every valid configuration is explored.

However, this approach becomes prohibitively expensive because each plot introduces multiple possibilities. In the worst case, the number of combinations grows exponentially with the size of the flowerbed. Since the array can contain up to 20,000 elements, this approach is completely impractical.

Optimal Greedy Approach

The key observation is that whenever a position is valid for planting, we should plant immediately.

Why is this safe?

If a plot can legally hold a flower, planting there never reduces our ability to place flowers later in a beneficial way. Since flowers cannot be adjacent, delaying a valid placement does not create a better future opportunity. Greedily planting as early as possible maximizes the total number of flowers we can place.

At each position, we only need to check three things:

  • The current plot is empty (0)
  • The left neighbor is empty, or the plot is at the start
  • The right neighbor is empty, or the plot is at the end

If all three conditions hold, we plant a flower, decrement n, and continue scanning.

As soon as n reaches 0, we can immediately return true.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Tries all planting combinations recursively
Optimal Greedy O(n) O(1) Scan once, greedily plant whenever valid

Algorithm Walkthrough

  1. Handle the trivial case where n == 0.

If no flowers need to be planted, we can immediately return true. 2. Iterate through the flowerbed from left to right.

At each index, determine whether planting a flower is legal. 3. Check whether the current plot is empty.

If flowerbed[i] == 1, skip it because it is already occupied. 4. Check the left side.

A flower can only be planted if the left neighbor is empty. For index 0, there is no left neighbor, so we treat it as valid.

We define:

left_empty = (i == 0 or flowerbed[i - 1] == 0) 5. Check the right side.

Similarly, the right neighbor must be empty. If the current plot is the final index, we treat the missing neighbor as empty.

We define:

right_empty = (i == len(flowerbed) - 1 or flowerbed[i + 1] == 0) 6. Plant a flower if both sides are valid.

If the current plot and both neighbors satisfy the rules, place a flower:

  • Set flowerbed[i] = 1
  • Decrement n

Updating the array is important because future checks must respect newly planted flowers. 7. Stop early if possible.

If n == 0, return true immediately since the goal has been achieved. 8. Finish scanning.

After the loop, return whether n <= 0.

Why it works

The algorithm works because of a greedy invariant: whenever a position can safely hold a flower, planting there cannot reduce the maximum number of flowers we can place later.

Since adjacency restrictions are purely local, a valid planting decision depends only on neighboring plots. Planting at the earliest possible valid position never blocks a better arrangement later, which means the greedy strategy always maximizes the number of flowers placed.

Therefore, if the greedy scan cannot place n flowers, no other arrangement can.

Python Solution

from typing import List

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

        length = len(flowerbed)

        for index in range(length):
            if flowerbed[index] == 0:
                left_empty = (
                    index == 0 or flowerbed[index - 1] == 0
                )
                right_empty = (
                    index == length - 1
                    or flowerbed[index + 1] == 0
                )

                if left_empty and right_empty:
                    flowerbed[index] = 1
                    n -= 1

                    if n == 0:
                        return True

        return n <= 0

The implementation begins with an early return for n == 0, since no work is required.

Next, we iterate through the flowerbed exactly once. For every empty plot, we check whether both neighboring plots are empty. Boundary indices are handled naturally by treating missing neighbors as empty.

When a valid position is found, we simulate planting by changing the value to 1. This modification is essential because future positions must respect flowers planted earlier in the iteration.

After planting, we decrement n. If n reaches zero, we return immediately, avoiding unnecessary work.

If the loop finishes and n is still positive, we know it was impossible to place enough flowers.

Go Solution

func canPlaceFlowers(flowerbed []int, n int) bool {
	if n == 0 {
		return true
	}

	length := len(flowerbed)

	for i := 0; i < length; i++ {
		if flowerbed[i] == 0 {
			leftEmpty := i == 0 || flowerbed[i-1] == 0
			rightEmpty := i == length-1 || flowerbed[i+1] == 0

			if leftEmpty && rightEmpty {
				flowerbed[i] = 1
				n--

				if n == 0 {
					return true
				}
			}
		}
	}

	return n <= 0
}

The Go implementation mirrors the Python logic almost exactly. Since Go slices are mutable, updating flowerbed[i] = 1 works naturally and ensures later checks see the modified state.

There are no concerns about integer overflow because all values remain very small and bounded by the input size. Go also does not distinguish between nil and empty slices in a way that matters here, since the constraints guarantee at least one element.

Worked Examples

Example 1

Input:

flowerbed = [1,0,0,0,1], n = 1
Index Flowerbed State Left Empty Right Empty Action n
0 [1,0,0,0,1] - - Already occupied 1
1 [1,0,0,0,1] No Yes Cannot plant 1
2 [1,0,0,0,1] Yes Yes Plant flower 0

Updated flowerbed:

[1,0,1,0,1]

Since n == 0, return true.

Example 2

Input:

flowerbed = [1,0,0,0,1], n = 2
Index Flowerbed State Left Empty Right Empty Action n
0 [1,0,0,0,1] - - Occupied 2
1 [1,0,0,0,1] No Yes Cannot plant 2
2 [1,0,0,0,1] Yes Yes Plant flower 1
3 [1,0,1,0,1] No No Cannot plant 1
4 [1,0,1,0,1] - - Occupied 1

Only one flower can be planted, so return false.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each plot is visited at most once
Space O(1) Only a few variables are used

The algorithm performs a single pass through the flowerbed array. Every position is checked once, and each check takes constant time. Since no auxiliary data structures proportional to input size are used, the extra memory remains constant.

Test Cases

solution = Solution()

assert solution.canPlaceFlowers([1, 0, 0, 0, 1], 1) is True  # example 1
assert solution.canPlaceFlowers([1, 0, 0, 0, 1], 2) is False  # example 2

assert solution.canPlaceFlowers([0], 1) is True  # single empty plot
assert solution.canPlaceFlowers([1], 1) is False  # single occupied plot
assert solution.canPlaceFlowers([0], 0) is True  # n = 0 edge case

assert solution.canPlaceFlowers([0, 0, 0, 0, 0], 3) is True  # maximum placements
assert solution.canPlaceFlowers([0, 0, 0, 0, 0], 4) is False  # exceeds capacity

assert solution.canPlaceFlowers([1, 0, 0, 0, 0, 1], 1) is True  # plant in middle
assert solution.canPlaceFlowers([1, 0, 0, 0, 0, 1], 2) is False  # not enough space

assert solution.canPlaceFlowers([0, 0, 1, 0, 0], 2) is True  # planting at edges
assert solution.canPlaceFlowers([1, 0, 1, 0, 1], 1) is False  # no valid spaces

assert solution.canPlaceFlowers([0, 0], 1) is True  # short even length
assert solution.canPlaceFlowers([0, 0], 2) is False  # adjacent violation

assert solution.canPlaceFlowers([0, 0, 0], 2) is True  # alternating placement
assert solution.canPlaceFlowers([0, 0, 0], 3) is False  # impossible request
Test Why
[1,0,0,0,1], 1 Verifies the first provided example
[1,0,0,0,1], 2 Verifies the second provided example
[0], 1 Tests single-element empty flowerbed
[1], 1 Tests single-element occupied flowerbed
[0], 0 Validates n = 0 behavior
[0,0,0,0,0], 3 Checks maximum greedy placements
[0,0,0,0,0], 4 Ensures impossible requests fail
[1,0,0,0,0,1], 1 Tests placement with interior spacing
[1,0,0,0,0,1], 2 Ensures adjacency constraints are respected
[0,0,1,0,0], 2 Tests planting near array boundaries
[1,0,1,0,1], 1 Verifies no valid placement exists
[0,0], 1 Small even-length array
[0,0], 2 Prevents adjacent planting
[0,0,0], 2 Tests alternating placements
[0,0,0], 3 Ensures over-requested placements fail

Edge Cases

Single Plot Flowerbed

A flowerbed of length one is easy to mishandle because there are no neighbors. For example, [0] should allow planting one flower, while [1] should not. A buggy implementation might attempt to access invalid indices.

This implementation handles the issue by treating missing neighbors as empty through the conditions index == 0 and index == length - 1.

Planting at the Boundaries

The first and last positions only have one real neighbor, making them common sources of off-by-one errors.

For example, in [0,0,1], the first position is valid because its right neighbor is empty and there is no left neighbor. Similarly, in [1,0,0], the final position can be planted.

The implementation explicitly treats nonexistent neighbors as empty, ensuring boundary placements work correctly.

Newly Planted Flowers Affect Future Decisions

A subtle bug occurs if the algorithm does not update the flowerbed after planting. Consider [0,0,0].

If we plant at index 0 but forget to mark it as occupied, index 1 might incorrectly appear available, violating the adjacency rule.

This implementation immediately updates flowerbed[index] = 1, ensuring future checks reflect newly planted flowers and maintain correctness.