605. Can Place Flowers Easy

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.

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

Approach

Input: A flowerbed array flowerbed, integer n.

Output: Whether n flowers can be planted without them being adjacent to each other.

This is an Array Traversal problem.

We iterate through the flowerbed, checking each time if a flower can be planted at the current position:

• The current plot is 0
• The left plot is empty or out of bounds
• The right plot is empty or out of bounds

• If conditions are met, plant a flower here (mark as 1) and decrement the required number n.
• During the iteration, if n <= 0, it means enough flowers have been successfully planted, immediately return true.
• If the iteration finishes and it's still not satisfied, return false.

Implementation

python

from typing import List

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        # Iterate through the flowerbed, checking if each position can plant a flower
        for i, flower in enumerate(flowerbed):
            # If the current position is empty, and both left and right are also empty, planting is allowed
            if (flower == 0 and 
                (i == 0 or flowerbed[i - 1] == 0) and 
                (i == len(flowerbed) - 1 or flowerbed[i + 1] == 0)):
                # Plant a flower at the current position
                flowerbed[i] = 1
                # Decrease the number of flowers needed to be planted by 1
                n -= 1
            
            # If enough flowers have been planted, directly return True
            if n <= 0:
                return True

        # If traversal finishes and enough flowers cannot be planted, return False
        return False

javascript

/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function(flowerbed, n) {
    let count = n;                 // Required number of flowers to be planted
    const len = flowerbed.length;  // Flowerbed length

    for (let i = 0; i < len; i++) {
        const f = flowerbed[i];    // Current plot's state (0 or 1)

        // If current position is empty, and neither adjacent plot has a flower
        if (
            f === 0 &&                                // Current is empty
            (i === 0 || flowerbed[i - 1] === 0) &&    // Left is empty or out of bounds (first plot)
            (i === len - 1 || flowerbed[i + 1] === 0) // Right is empty or out of bounds (last plot)
        ) {
            flowerbed[i] = 1; // Plant flower at current position
            count--;          // Required count decrements by one
        }

        // If enough have been planted, return true early
        if (count <= 0) return true;
    }

    // Traversal finished but still not enough planted, return false
    return false;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1) (or O(n) if considering modification on the original structured array or input nature)

Links

605. Can Place Flowers (English)

605. 种花问题 (Chinese)