Problem Description

You have a flowerbed represented as an array where some plots already have flowers planted and some are empty. The constraint is that flowers cannot be planted in adjacent plots - there must be at least one empty plot between any two flowers.

The flowerbed is given as an integer array flowerbed where:

• 0 represents an empty plot
• 1 represents a plot with a flower already planted

Given this flowerbed array and an integer n, you need to determine if it's possible to plant n additional flowers in the flowerbed while following the no-adjacent-flowers rule.

For a flower to be planted at position i, three conditions must be met:

1. The current position flowerbed[i] must be empty (value is 0)
2. The left adjacent position flowerbed[i-1] must be empty or not exist (for the first position)
3. The right adjacent position flowerbed[i+1] must be empty or not exist (for the last position)

Return true if you can successfully plant all n flowers without violating the adjacency rule, and false otherwise.

For example, if flowerbed = [1,0,0,0,1] and n = 1, you can plant one flower at position 2 (making it [1,0,1,0,1]), so the answer would be true. But if n = 2, you cannot plant two flowers without violating the rule, so the answer would be false.

Intuition

The key insight is that we want to maximize the number of flowers we can plant. Since we need to maintain gaps between flowers, the best strategy is to plant flowers as soon as we find a valid spot - this is a greedy approach.

Think of it this way: if we skip a valid planting spot now, we might not get a better opportunity later. By planting immediately when possible, we ensure we're using every available space optimally.

The challenge with checking boundaries is handling the edge cases - what happens at the beginning and end of the flowerbed? A clever trick is to add virtual empty plots [0] at both ends of the array. This padding simplifies our logic because:

• For the first real position, we now have a left neighbor to check (the virtual 0)
• For the last real position, we now have a right neighbor to check (the virtual 0)

With this padding, we can use a uniform checking rule for all positions: a position is valid for planting if the sum of three consecutive values (left, current, right) equals 0. This means all three positions are empty.

Once we find such a spot, we immediately plant a flower there (set it to 1) and decrease our counter n. This greedy planting ensures that we don't miss any opportunity and also automatically prevents future adjacent planting since we've marked the spot as occupied.

The beauty of this approach is its simplicity - we make one pass through the array, make local decisions based on immediate neighbors, and these local optimal choices lead to the global optimal solution.

Learn more about Greedy patterns.

Solution Approach

The implementation uses a greedy algorithm with array padding for boundary handling. Let's walk through the solution step by step:

Step 1: Padding the Array

flowerbed = [0] + flowerbed + [0]

We add a 0 at the beginning and end of the flowerbed array. This eliminates the need for special boundary checks when examining adjacent positions.

Step 2: Traverse and Plant

for i in range(1, len(flowerbed) - 1):

We iterate through the padded array from index 1 to len(flowerbed) - 2 (the original flowerbed positions). The padding ensures we never go out of bounds when checking neighbors.

Step 3: Check Planting Condition

if sum(flowerbed[i - 1 : i + 2]) == 0:

For each position i, we check if we can plant a flower by summing three consecutive elements: flowerbed[i-1], flowerbed[i], and flowerbed[i+1]. If the sum equals 0, it means:

• The current position is empty (flowerbed[i] = 0)
• The left neighbor is empty (flowerbed[i-1] = 0)
• The right neighbor is empty (flowerbed[i+1] = 0)

Step 4: Plant and Update Counter

flowerbed[i] = 1
n -= 1

When we find a valid spot, we immediately:

• Plant a flower by setting flowerbed[i] = 1
• Decrement the counter n by 1

This greedy planting ensures that future iterations will see this position as occupied, automatically preventing adjacent planting.

Step 5: Return Result

return n <= 0

After traversing the entire array, if n <= 0, it means we've successfully planted all required flowers (or more spots were available than needed), so we return true. Otherwise, we return false.

The time complexity is O(n) where n is the length of the flowerbed, as we traverse the array once. The space complexity is O(n) due to the padded array creation.

Example Walkthrough

Let's walk through the solution with flowerbed = [1,0,0,0,1] and n = 1.

Step 1: Add padding

Original: [1,0,0,0,1]
Padded:   [0,1,0,0,0,1,0]
           ↑           ↑
        padding     padding

Step 2: Iterate through original positions (indices 1-5 in padded array)

• i = 1: Check [0,1,0]

  • Sum = 0 + 1 + 0 = 1 (not equal to 0)
  • Cannot plant here (already has a flower)

• i = 2: Check [1,0,0]

  • Sum = 1 + 0 + 0 = 1 (not equal to 0)
  • Cannot plant here (left neighbor has a flower)

• i = 3: Check [0,0,0]

  • Sum = 0 + 0 + 0 = 0 ✓
  • Can plant! Set flowerbed[3] = 1
  • Decrement n: n = 1 - 1 = 0
  • Padded array becomes: [0,1,0,1,0,1,0]

• i = 4: Check [1,0,1]

  • Sum = 1 + 0 + 1 = 2 (not equal to 0)
  • Cannot plant here (both neighbors have flowers)

• i = 5: Check [0,1,0]

  • Sum = 0 + 1 + 0 = 1 (not equal to 0)
  • Cannot plant here (already has a flower)

Step 3: Check result

• n = 0, which is ≤ 0
• Return true - we successfully planted all required flowers!

The final flowerbed (without padding) would be [1,0,1,0,1].

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the original flowerbed array. The algorithm performs the following operations:

• Creating an extended array with padding: O(n)
• Iterating through the extended array once: O(n)
• For each position, calculating the sum of 3 elements: O(1)

Overall, the time complexity remains O(n) as we traverse the array once.

The space complexity is O(n), not O(1) as stated in the reference answer. This is because the code creates a new array flowerbed = [0] + flowerbed + [0], which creates a copy of the original array with two additional elements. This requires O(n) extra space where n is the length of the original flowerbed array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying the Original Array

The current solution modifies the input flowerbed array by creating a new padded version and planting flowers in it. While this works for the algorithm, it doesn't preserve the original input, which could be problematic if:

• The caller expects the original array to remain unchanged
• You need to use the original array state after the function call
• The problem explicitly states not to modify the input

Solution: Create a copy of the array before modification:

def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
    # Create a copy to avoid modifying the original
    flowerbed = [0] + flowerbed[:] + [0]  # flowerbed[:] creates a shallow copy
    # ... rest of the code remains the same

2. Inefficient Space Usage with Array Padding

The padding approach creates a new array with O(n) extra space. For very large arrays, this could be memory-intensive.

Solution: Use explicit boundary checking without padding:

def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
    for i in range(len(flowerbed)):
        # Check if current spot is empty
        if flowerbed[i] == 0:
            # Check left boundary (i == 0 means no left neighbor)
            left_empty = (i == 0) or (flowerbed[i - 1] == 0)
            # Check right boundary (i == len-1 means no right neighbor)
            right_empty = (i == len(flowerbed) - 1) or (flowerbed[i + 1] == 0)
          
            if left_empty and right_empty:
                flowerbed[i] = 1
                n -= 1
                if n <= 0:  # Early termination optimization
                    return True
    return n <= 0

3. Missing Early Termination

The current solution continues checking even after planting all required flowers. This is inefficient when n is small compared to the flowerbed size.

Solution: Add an early return condition:

def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
    # Handle edge case early
    if n == 0:
        return True
      
    flowerbed = [0] + flowerbed + [0]
  
    for i in range(1, len(flowerbed) - 1):
        if sum(flowerbed[i - 1 : i + 2]) == 0:
            flowerbed[i] = 1
            n -= 1
            # Early termination when all flowers are planted
            if n == 0:
                return True
  
    return False

4. Slice Operation Overhead

Using sum(flowerbed[i - 1 : i + 2]) creates a new list slice and then sums it, which adds unnecessary overhead for checking just three elements.

Solution: Use direct element access:

def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
    flowerbed = [0] + flowerbed + [0]
  
    for i in range(1, len(flowerbed) - 1):
        # Direct element checking is more efficient than slice + sum
        if flowerbed[i - 1] == 0 and flowerbed[i] == 0 and flowerbed[i + 1] == 0:
            flowerbed[i] = 1
            n -= 1
            if n == 0:
                return True
  
    return n <= 0