Watch 10 video solutions for Can Place Flowers, a easy level problem involving Array, Greedy. This walkthrough by NeetCode has 64,362 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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
Constraints:
1 <= flowerbed.length <= 2 * 104flowerbed[i] is 0 or 1.flowerbed.0 <= n <= flowerbed.lengthProblem Overview: You are given a binary array flowerbed where 1 means a flower is already planted and 0 means empty. You need to determine whether you can plant n new flowers without violating the rule that no two flowers can be adjacent.
Approach 1: Counting Possible Placements (O(n) time, O(1) space)
This method analyzes stretches of consecutive empty plots and calculates how many flowers can fit inside each segment. If you find a block of k zeros surrounded by planted flowers, the maximum placements inside that segment follow a predictable pattern: you can place (k-1)/2 flowers. Edge segments (start or end of the array) allow slightly more placements because only one side has a restriction. The algorithm scans the array once, counts zero segments, and accumulates the total possible placements. If the sum reaches or exceeds n, planting is feasible. The logic is purely arithmetic on segments, which keeps the time complexity O(n) and space complexity O(1). This technique works well when reasoning about contiguous gaps in an array.
Approach 2: Greedy Planting by Scanning (O(n) time, O(1) space)
The greedy approach directly simulates planting while scanning the array from left to right. For each index i, check three conditions: the current plot is empty, the left neighbor is empty (or doesn't exist), and the right neighbor is empty (or doesn't exist). If all conditions hold, plant a flower by setting flowerbed[i] = 1 and decrease n. This works because placing a flower as early as possible never blocks a better future placement. The algorithm only performs constant-time checks per position, so the total runtime is O(n) with O(1) extra space. This is a classic example of a greedy decision: a locally optimal placement leads to a globally optimal result.
During the scan you simply iterate once through the array, perform neighbor checks, and update the state when planting occurs. The modification is safe because once a flower is placed, the next index automatically becomes invalid for planting, which the neighbor checks naturally enforce.
Recommended for interviews: The greedy scanning approach is what interviewers typically expect. It shows you can reason about constraints directly and implement a linear pass with constant space. The counting approach demonstrates deeper pattern recognition with segments and boundaries, which can help when generalizing similar gap counting problems in array processing.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting Possible Placements | O(n) | O(1) | When analyzing zero segments or reasoning mathematically about placement capacity |
| Greedy Planting by Scanning | O(n) | O(1) | General case and most common interview solution using greedy checks |