Problem
Given an integer array flowerbed containing0s and 1s, where 0 represents an empty plot and 1 represents a plot that already contains a flower, determine whether n new flowers can be planted without violating the rule that no two flowers can be placed in adjacent plots. Return
true if all n flowers can be planted; otherwise, return false.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
flowerbed = [1,0,0,0,1]
n = 1Output
trueSolution
This solution uses a Greedy approach. We traverse the flowerbed from left to right and plant a flower whenever the current position and its adjacent positions are empty.For each position, we check three conditions: the current position must be
0, the previous position must either not exist or be 0, and the next position must either not exist or be 0. When all three conditions are satisfied, we immediately plant a flower by changing the current value to
1 and decrease n. Modifying the array ensures that the next position correctly recognizes the newly planted flower. The process stops early and returns
true as soon as all required flowers have been planted.
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
if (n == 0)
return true;
int m = flowerbed.length;
for (int i = 0; i < m; i++) {
if (flowerbed[i] == 0
&& (i == 0 || flowerbed[i - 1] == 0)
&& (i == m - 1 || flowerbed[i + 1] == 0)) {
flowerbed[i] = 1;
n--;
}
if (n == 0)
return true;
}
return false;
}
}Complexity
The flowerbed is traversed at most once, and each position requires only constant-time checks. Therefore, the time complexity isO(n), where n is the length of the flowerbed.
The algorithm modifies the input array directly and uses only a constant number of variables, so the extra space complexity is
O(1).