Leetcode 605. Can Place Flowers

Problem

You are managing a garden plot represented as an array where each position either contains a planted flower (1) or is empty (0). The garden has a strict rule: no two flowers can be planted in adjacent positions.

Given the current state of the garden and a number of new flowers you want to plant, determine whether it's possible to plant all the new flowers while respecting the adjacency rule.

Requirements

1. Return true if you can plant n new flowers without violating the adjacency constraint
2. Return false if it's impossible to plant all n flowers
3. You must not modify any existing flowers (positions with value 1)
4. A flower can only be planted in an empty spot (0) where both neighbors are also empty (or the spot is at an edge)

Constraints

• 1 ≤ flowerbed.length ≤ 20,000
• flowerbed[i] is either 0 or 1
• There are no two adjacent flowers in the input array
• 0 ≤ n ≤ flowerbed.length

Examples

Example 1:

Input: flowerbed = [1, 0, 0, 0, 1], n = 1 Output: true Explanation: We can plant one flower at index 2. The neighbors at indices 1 and 3 are both empty (0).

Example 2:

Input: flowerbed = [1, 0, 0, 0, 1], n = 2 Output: false Explanation: Only one flower can be planted (at index 2). We cannot plant 2 flowers without creating adjacent plants.

Example 3:

Input: flowerbed = [0, 0, 0], n = 2 Output: true Explanation: We can plant flowers at index 0 and index 2, leaving index 1 empty as a buffer.

Example 4:

Input: flowerbed = [0], n = 1 Output: true Explanation: A single empty plot can accommodate one flower since it has no neighbors.

Hint 1: Greedy Strategy A greedy approach works well here. Try to plant flowers as early as possible in the array whenever you find a valid spot. This maximizes the number of flowers you can plant overall.

Hint 2: Valid Planting Conditions A position i is valid for planting if:

• flowerbed[i] is currently 0 (empty)
• The left neighbor (if it exists) is 0
• The right neighbor (if it exists) is 0

Be careful with edge cases at the boundaries of the array!

Hint 3: Early Termination You don't need to scan the entire array. Once you've successfully planted n flowers, you can return true immediately.

Full Solution `` Approach:

This solution uses a greedy algorithm that scans through the flowerbed from left to right. At each empty position, it checks whether both neighbors (if they exist) are also empty. If so, it plants a flower and increments the counter.

Key Insights:

1. Greedy works: Planting as early as possible never hurts our chances of planting more flowers later
2. Edge handling: Positions at index 0 and the last index only have one neighbor to check
3. Optimization: We can return early once we've planted enough flowers

Time Complexity: O(n) where n is the length of the flowerbed array. We make a single pass through the array.

Space Complexity: O(1) as we only use a constant amount of extra space (we modify the input array in place, but this doesn't count toward space complexity).