Solution


Approach #1 Single Scan [Accepted]

The solution is very simple. We can find out the extra maximum number of flowers, , that can be planted for the given arrangement. To do so, we can traverse over all the elements of the and find out those elements which are 0(implying an empty position). For every such element, we check if its both adjacent positions are also empty. If so, we can plant a flower at the current position without violating the no-adjacent-flowers-rule. For the first and last elements, we need not check the previous and the next adjacent positions respectively.

If the obtained is greater than or equal to , the required number of flowers to be planted, we can plant flowers in the empty spaces, otherwise not.

Complexity Analysis

  • Time complexity : . A single scan of the array of size is done.

  • Space complexity : . Constant extra space is used.


Approach #2 Optimized [Accepted]

Algorithm

Instead of finding the maximum value of that can be obtained, as done in the last approach, we can stop the process of checking the positions for planting the flowers as soon as becomes equal to . Doing this leads to an optimization of the first approach. If never becomes equal to , flowers can't be planted at the empty positions.

Complexity Analysis

  • Time complexity : . A single scan of the array of size is done.

  • Space complexity : . Constant extra space is used.


Analysis written by: @vinod23