#605

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Can Place Flowers

Determine if n new flowers can be planted in a flowerbed, ensuring no adjacent flowers using a greedy approach.

Problem Statement

You are given an integer array representing a flowerbed, where 1 means a flower is already planted and 0 means the plot is empty. The goal is to determine if n new flowers can be planted in the flowerbed while respecting the no-adjacent-flowers rule.

To achieve this, iterate through the flowerbed and try to plant a flower in each empty plot. For each empty plot (0), ensure that no adjacent plots are already occupied by flowers. If n flowers can be placed successfully, return true. Otherwise, return false.

Examples

Example 1

Input: flowerbed = [1,0,0,0,1], n = 1

Output: true

Example details omitted.

Example 2

Input: flowerbed = [1,0,0,0,1], n = 2

Output: false

Example details omitted.

Constraints

1 <= flowerbed.length <= 2 * 104
flowerbed[i] is 0 or 1.
There are no two adjacent flowers in flowerbed.
0 <= n <= flowerbed.length

Solution Approach

Greedy Approach

Iterate through the flowerbed, checking each plot. For each empty plot (0), check if both adjacent plots are empty or out of bounds. Plant the flower if possible, and decrement n. If n reaches 0, return true.

Early Termination

Once n reaches 0, stop checking the rest of the flowerbed and return true immediately. This saves time as further checking is unnecessary when enough flowers have been planted.

Boundary Handling

Ensure that edge cases like the first and last plots are handled correctly by considering boundary conditions and ensuring no out-of-bounds errors occur when checking adjacent plots.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity is O(n) because the flowerbed array is iterated once. The space complexity is O(1) since only a constant amount of extra space is used for tracking flower placement.

What Interviewers Usually Probe

Candidate demonstrates understanding of greedy algorithms.
Candidate is able to explain the importance of early termination and boundary conditions.
Candidate can handle edge cases involving small or large flowerbed arrays.

Common Pitfalls or Variants

Common pitfalls

Failing to account for boundary conditions (first and last plot).
Incorrectly attempting to plant flowers in adjacent plots, violating the rule.
Not terminating early when enough flowers are planted.

Follow-up variants

What if we need to plant more than one flower in a single pass?
What if the flowerbed array is larger or smaller than typical inputs?
How would the approach change if the flowerbed could have more complex rules, such as spacing requirements between flowers?

FAQ

How do I know when to stop planting flowers in the 'Can Place Flowers' problem?

You can stop planting flowers once n reaches 0, indicating that all required flowers have been placed.

What is the time complexity of the 'Can Place Flowers' problem?

The time complexity is O(n), where n is the length of the flowerbed array, because each plot is checked once.

Why is it important to handle boundary conditions in this problem?

Boundary conditions are crucial because the first and last plots may not have two adjacent plots to check, and overlooking this can lead to errors.

What is the greedy approach used in the 'Can Place Flowers' problem?

The greedy approach places flowers in each empty plot (0), ensuring no adjacent flowers are placed, and stops once the required number of flowers is planted.

How can GhostInterview help me solve problems like 'Can Place Flowers'?

GhostInterview offers a detailed, step-by-step guide to solving problems with a focus on greedy algorithms, boundary handling, and interview-ready solutions.

terminal

Solution

Solution 1: Greedy

We directly traverse the array $flowerbed$. For each position $i$, if $flowerbed[i]=0$ and its adjacent positions on the left and right are also $0$, then we can plant a flower at this position. Otherwise, we cannot. Finally, we count the number of flowers that can be planted. If it is not less than $n$, we return $true$, otherwise we return $false$.

1

2

3

4

5

6

7

8

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        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
        return n <= 0

Continue Practicing

#611 valid triangle number #621 task scheduler #624 maximum distance in arrays