Suppose 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 - they would compete for water and both would die.
Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.
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
Note:
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.
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