LeetCode Challenge #605. Can Place Flowers

Question 4 of 75 - LeetCode Weekly Challenge

LeetCode Challenge #605. Can Place Flowers

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

Video Solution

C++ Solution

				
					class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {

        int size= flowerbed.size();
        int i=0;

        if(n>size)return false;
        if(size==1) return ((n==1 and flowerbed[0]==0)||(n==0));
        
        while(i<size)
        {
            if(flowerbed[i]==0)
            {
                if(i==0)
                {
                    if(flowerbed[i+1]==0)
                    {
                        flowerbed[i]=1;
                        n--;
                    }
                }
                else if(i==size-1)
                {
                    if(flowerbed[i-1]==0)
                    {
                        flowerbed[i]=1;
                        n--;
                    }
                }
                else
                {
                    if(flowerbed[i+1]==0 and flowerbed[i-1]==0)
                    {
                        flowerbed[i]=1;
                        n--;
                    }
         
            i++;
        }

        if(n<=0)return true;
        return false;
    }
};

Code Explanation

We are here provided with a plant bed in which few of the plants are already planted and few of them are not, and we have to plant new flowers in the bed . There should be a vacant place for a flower to be planted otherwise we cannot do the same .

Also, we have to keep in mind to place flower in such a position that it should have no adjacent plants .

Here 0 represents empty plot and 1 represents a planted flower.

Let’s see the approach step by step –

Here ‘Int n’ represents the number of new flowers to be planted.

To Determine the size of the flowerbed , we will make a variable (‘int size’) to know the actual size of flowerbed. We have also taken an iterator (‘i’) which starts from 0.

If the number of flowers that has to be planted are greater than the size of flowerbed. Then definitely it’s impossible to plant to plant ‘n’ flowers in the flowerbed. That is why we return ‘false’ here.

Now , if the size of flowerbed is one , the space should be vacant in flowerbed for that one plant (flowerbed[0]==0) then we check two conditions:
The size of n should be one (n==1) ; then its possible to plant the flower , so it returns ‘true’ .
If (n==0) , it means no flower need to be planted , so it returns ‘true’ in this case also.

Within the loop , the iterator should be less than size (iterator< size)

The loops checks several conditions like:

If the current plot is empty (0) , it checks the adjacent plots (left and right) are also empty , then we can place the flower (flowerbed[ i ] =1) , And when we have placed a flower the total count of ‘n’ will be reduced i.e (“ n- – “).

If the current position is at the beginning ( i==0) then it only checks the right position by [ flowerbed( i +1)==0 ] to ensure it’s empty

Now if the current iterator is at the last place , we have to check the ( i -1) position

By [ flowerbed( i-1)==0]

If this is true that means we can plant the flower and quantity of n number of flowers will be reduced by one.

If the flower is placed in the middle of flowerbed its both the adjacent sides should be vacant , that means

If [ i+1==0 ] position and

[ i -1==0 ] position is vacant then the flower can be planted here .

And if the current position has already a flower planted then we simply do [ i++] .

In this way the loop works, at last it checks if ( n<=0 ) ; i.e,

If n is less than or equal to 0 , it means that all the flowers have been planted , and the function returns ‘true’ . Otherwise it returns ‘false’ .

Question 4 of 75 - LeetCode Weekly Challenge