Arrays - 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.

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true
Explanation: 1 flower can be placed at index 2.

Input: flowerbed = [1,0,0,0,1], n = 2
Output: false
Explanation: 1 flower can be placed at index 2, but there is no spot for 2nd flower, so the answer is false.

Solution using one pass iteration through elements and check left and right side elements

In this approach, we are going to iterate through elements of input array flowerbed and check if left side element and right side elements are 0's, then we can place a flower at that index.

Special handling for left most element and right most elements:

If we are at index 0, then there is nothing to check on left side, so we just check whether right side element is 0.
If we are at index flowebed.length -1, there there is nothing to check on right side, so we just check whether left side element is 0.

public class CanPlaceFlowers { static boolean canPlace(int[] flowerbed, int n) { int i = 0; while(i<flowerbed.length && n>0) { if(flowerbed[i] == 0 && (i == 0 || flowerbed[i-1] ==0) && (i==flowerbed.length-1 || flowerbed[i+1]==0)) { n--; flowerbed[i] = 1; } i++; } return n==0; } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input array flowerbed length.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code

Contents

Complexity Analysis: