can place flower — leetCode Problem

Description

You are given an array which represent a flowerbed, each cell of the array is plot some of the plots are already planted and in array those plots are represented by 1 and some plots are blank represented by 0. You can plant a flower in a plot if following condition satisfied

1. If it is blank (means no plant already )
2. If its adjacent plots are blank

You have to tell whether we can plant “n’” ( provided in the input ) number of flowers or not.

Input

flowerbedArray, numberOfFlowers

How to approach the solution?

To begin is the toughest step towards reaching a solution, It is better to read the problem carefully and understand, what are the constraints and demands of the problem.

In above problem we have to check whether we can plan n flowers or not in given flowerbed.

In other words i need to find n cells which are satisfying all the conditions or constrains mentioned in the problem.

To do so i can Iterate through array and check :

1. if the plot flowerbed[i] is empty or not?
2. if it is empty then, is there any adjacent plot already have flowers ? left sided flowerbed[i-1] and right side flowerbed[i+1] should be empty.
3. if above condition satisfied plot the plant and reduce the number of plants to be planted by 1.
4. Repeat this for every element till end of array

at the end check if n>0 then it means we failed to plant all the flowers hence return false else return true.

while accessing the array should keep in mind that index not overshoot the range.

Below is the implementation of the above logic

This solution works well and do the job and complexity is also O(n) order but still there is space for improvement. We can remove some condition put it out of the loop and add some more code and thus can reduce the overhead of processing .

Here is the improvised code

Still if you see we are updating the input array inside the loop. We can get rid of this if we simply count the eligible places and then applying some mathematics

if there are n places we can fill n/2 places if n is even and (n+1)/2 if n is odd

since in c++ n/2 results in integer answer you should not be care about odd and even if we simply use (n+1)/2.

adding some more code and modification we can optimize it further.

here is the more optimized code

Thanks for reading :)