Problem

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 if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule.

Examples

Example 1:

1
2
3
4

Input:
flowerbed = [1,0,0,0,1], n = 1
Output:
 true

Example 2:

1
2
3
4

Input:
flowerbed = [1,0,0,0,1], n = 2
Output:
 false

Solution

Method 1 - Greedy approach - Add 2 spots to flowerbed

Lets see examples [1, 0, 1] -> We cannot place flower, as sides already are bounded by flower [1, 0, 0, 1] -> We cannot place flower [1, 0, 0, 0, 1] -> We can now place the flowers So, we need atleast 3 empty space to put 1 flower, 5 to place 2 and so on;

But there is a problem, what if array doesn’t start with 0 OR end with 0? For eg. [0, 0, 1] -> Now we can place the flower at index 0.

So, its good to assume 2 empty spots before 0th and last index of array.

So, we can append these to the array and proceed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public boolean canPlaceFlowers(int[] flowerbed, int n) {
	int arr = new int[flowerbed.length + 2];
	for(int i = 1; i < arr.length - 1; i++){
		arr[i] = flowerbed[i-1];
	}

	for(int i = 1; i < arr.length - 1; i++){
		if(arr[i-1] == 0 && arr[i] == 0 && arr[i+1]==0){
			arr[i] = 1; // place the flower
			n--; // reduce the num flowers
		}
	}

	return n <= 0;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 2 - Using Greedy approach without using aux array

We can also do it without creating extra array, we can also just take care of the side conditions.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public boolean canPlaceFlowers(int[] flowerbed, int n) {
	int m = flowerbed.length;

	if (m == 1 && flowerbed[0] == 0) {
		return true;
	}

	if (flowerbed[0] == 0 && flowerbed[1] == 0) {
		flowerbed[0] = 1;
		n--;
	}

	if (flowerbed[m - 1] == 0 && flowerbed[m - 2] == 0) {
		flowerbed[m - 1] = 1;
		n--;
	}

	for (int i = 1; i < m - 1; i++) {
		if (flowerbed[i - 1] == 0 && flowerbed[i] == 0 && flowerbed[i + 1] == 0) {
			flowerbed[i] = 1;
			n--;
		}
	}

	return n <= 0;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 3 - Greedy by counting continuous flowerbed points

We can just count number of flowerbed points that are empty continuously.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public boolean canPlaceFlowers(int[] flowerbed, int n) {
	int empty = flowerbed[0] == 0 ? 1: 0;
	
	for(int f: flowerbed){
		if (f == 1){
			n -= (empty-1)/2;
			empty = 0; // reset empty
		}else {
			empty++;
		}
	}
	// tricky bit
	n -= empty / 2; // we are now at last point, so we add 1 as we assume boundary after arr.length-1. So, we remove -1 this time, while reducing number of flowers

	return n <= 0;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)