Can Place Flowers LeetCode Solution

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Bloomberg Facebook LinkedIn Microsoft YahooViews 8030

Problem Statement

Can Place Flowers LeetCode 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 if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule.

Example

Test Case 1:

Input:

flowerbed = [1,0,0,0,1],

n = 1

Output:

true

Approach:

Let’s consider a very simple case where we have a bunch of 0s ending with 1.

Example:

01

001

0001

00001

We can plant only in the l = arr.size() – 2 zeros. A total number of plants that can be planted in such a section = Math.ceil(l/2D) Now we can imagine the whole array composed of such partitions.

Example

[1,0,0,0,1]

[1,0] [0,0,1]

Solution: Linearly scan through the array always incrementing the size of the window. Whenever we encounter 1, we calculate the number of plants possible in that subarray.

  1. we use two-point start, end to record the ith empty pilot’s left and right flower position
  2. for ith pilot, we calculate the distance to the left (i-start)and to right(end-i) and get the min distance
  3. if min distance >=2 we can say that this pilot can be placed as a flower.
  4. then we set ith pilot as 1, which means that this pilot has been placed and we reset the start point to i and decrement n
  5. if n==0 which means all flowers have been placed

Special case;

  1. If the first or last position is 0, it means that the left or right side has not been spent. At this time we set start or end to length of the array, because we need to find the minimum distance between the two sides of the empty position. At this time, the left position and the right position can seem infinitely large.
  2. If n=0, it returns true by default.

3. [0],1 This case also returns true by default.

Code for Can Place Flowers

Java Program

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        int first = -2;
        int second = 0;
        while(second < flowerbed.length){
            while(second < flowerbed.length && flowerbed[second] != 1){
                second ++;
            }
            if(second >= flowerbed.length){break;}
            count += (second-first-2)/2;
            
            first = second;
            
            second ++;
        }
        System.out.println(second);
        count += (second-first-1)/2;
        return count >= n;
    }
}

C++ Program

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int count = 0 ;
        int s = flowerbed.size();
        for(int i = 0 ; i < s ; i++ ){
            if(flowerbed[i] == 0){      // when a place is
                bool leftflag = (i == 0) || (flowerbed[i-1] == 0);  //check whether left is empty 
                bool rightflag = (i == s-1) || (flowerbed[i+1] == 0); //check whether left is empty 
                
                if(leftflag && rightflag){  // updation
                    flowerbed[i] = 1;
                    count++;
                    if(count >= n){
                        return true;
                    }
                }
            }
        }
        return count>=n;
    }
};

Complexity Analysis for Can Place Flowers LeetCode Solution

Time Complexity: O(n) as we are just iterating the array once.

Space Complexity: O(1) as we are not using any extra space.

Translate »