Scale Engineer

Can Place Flowers

Easy
#0571Time: O(N), where N is the number of plots in the flowerbed. We iterate through the array once.Space: O(N), for the copy of the `flowerbed` array.8 companies
Patterns
Greedy
Data structures
Array
Companies
AgodaAirbnbAtlassianCisco

Prompt

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 * 104
  • flowerbed[i] is 0 or 1.
  • There are no two adjacent flowers in flowerbed.
  • 0 <= n <= flowerbed.length

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iterating through the flowerbed and checking each empty plot to see if a flower can be planted. To avoid issues with modifying the array while iterating, a copy of the flowerbed is made. We count the total number of new flowers that can be planted and then compare this count with n.

Algorithm

  • If n is 0, return true immediately.
  • Create a copy of the flowerbed array to avoid modifying the original array while iterating.
  • Initialize a counter count to 0, which will track the number of flowers planted.
  • Iterate through the copied flowerbed from the first plot to the last.
  • For each plot i, if it's empty (flowerbed[i] == 0):
    • a. Check if the previous plot is empty. This condition is met if i is the first plot (i == 0) or if flowerbed[i - 1] == 0.
    • b. Check if the next plot is empty. This condition is met if i is the last plot (i == flowerbed.length - 1) or if flowerbed[i + 1] == 0.
    • c. If both neighboring plots are empty, plant a flower by setting flowerbed[i] = 1 in the copy and increment count.
  • After planting a flower, check if count has reached n. If it has, we can stop early and return true.
  • If the loop completes, return true if count >= n and false otherwise.

Walkthrough

The core idea is to simulate the process of planting flowers without altering the original array during the decision-making process for each plot. We create a temporary copy of the flowerbed array. Then, we iterate through the flowerbed from left to right. For each empty plot flowerbed[i] == 0, we check its neighbors. The neighbors are at i-1 and i+1. We must handle the edge cases where i is 0 or the last index. If a plot at index i is empty and both its neighbors are also empty (or it's an edge), we can plant a flower there. We increment a counter for planted flowers and update the copy of the array at index i to 1. This ensures that when we check the next plot, our decision is based on the updated state of the flowerbed. Finally, we check if the total count of flowers we could plant is greater than or equal to n.

class Solution {    public boolean canPlaceFlowers(int[] flowerbed, int n) {        if (n == 0) {            return true;        }        int[] temp = new int[flowerbed.length];        System.arraycopy(flowerbed, 0, temp, 0, flowerbed.length);                int count = 0;        for (int i = 0; i < temp.length; i++) {            if (temp[i] == 0) {                // Check previous plot                boolean prevEmpty = (i == 0) || (temp[i - 1] == 0);                // Check next plot                boolean nextEmpty = (i == temp.length - 1) || (temp[i + 1] == 0);                                if (prevEmpty && nextEmpty) {                    temp[i] = 1; // Plant the flower in the copy                    count++;                    if (count >= n) {                        return true;                    }                }            }        }        return count >= n;    }}

Complexity

Time

O(N), where N is the number of plots in the flowerbed. We iterate through the array once.

Space

O(N), for the copy of the `flowerbed` array.

Trade-offs

Pros

  • Conceptually simple and easy to follow.

  • Avoids modifying the original input array.

Cons

  • Uses extra space proportional to the size of the input, which is inefficient for large flowerbeds.

Solutions

class Solution { public boolean canPlaceFlowers ( int [] flowerbed , int n ) { int m = flowerbed . length ; for ( int i = 0 ; i < m ; ++ i ) { int l = i == 0 ? 0 : flowerbed [ i - 1 ]; int r = i == m - 1 ? 0 : flowerbed [ i + 1 ]; if ( l + flowerbed [ i ] + r == 0 ) { flowerbed [ i ] = 1 ; -- n ; } } return n <= 0 ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem