Planting flowers with no adjacent flower plots

Problem

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 booleans), return if a given number of new flowers can be planted in it without violating the no-adjacent-flowers rule 

Sample inputs 

Input: 1,0,0,0,0,0,1,0,0 

3 => true 

4 => false 

Input: 1,0,0,1,0,0,1,0,0 

1 => true 

2 => false 

input: 0 

1 => true 

2 => false 

public boolean canPlaceFlowers(List flowerbed, int numberToPlace) { 

// Implementation here 

}

Answer

Brute-force approach, $O(N \times N!)$

   The first idea that came to my mind after understanding this question was to use DFS to find the best possible way to plant the flowers.
  Using DFS with the backtracking, we can easily determine whether a given target number of flowers can be planted. However, this will potentially take $O(N \times N!)$.

This is way too slow, which led me to the next solution, which I was able to complete in 32 mins.

Dynamic programming, O(N)

 In dynamic programming, we need to:

• 1. image the ideal solution, $S_{n}$, where n is the last pot in the flowerbed.
• Given the restriction of consecutive planting, the possible max number of pots $S_{n}$ can be written as below: $$S_{n} = MAX(S_{n-1}, S_{n-2} + W_{n}$$ where $W_{n}$ is 1 if n th pot is plantable, - $\infty$.
• 2. build up the loop from the beginning based on the ideal solution by filling in the $S_{i}$ following the formula below: $$S_{i} = MAX(S_{i-1}, S_{i-2} + W_{i}$$

• 3. backtrace the solution by walking the array S if necessary

Linear search with preprocessing ( not working)

I could not come up with a better name so I stated merely what the algorithm does.
Instead of using DFS, we can preprocess to identify the available empty plot in the flowerbed.

Figure1. Example algorithm

Step 1: 
  As you can see in Figure 1, we first mark the all unavailable plot in the flower bed.  Any plots right before and after the occupied plot (marked as 1) are marked as 1.

Step 2:
   We now compile the list of consecutive empty plots (a cluster) by scanning the list.

Step 3:
    We now scan the list of clusters of empty slots and calculate the number of flowers to plants as below:
              Maximum number of flows to plants, M = $\lceil \text{number of empty plots} \rceil$

 We can continue to subtract the M from the target count while scanning the list of clusters.
This algorithm will take $O (N)$, where N is the length of the floor bed.

UPDATE(2022-06-28): After reviewing the original algorithm, I found that the original algorithm with the preprocessing has a bug. If empty slots after pre-processing are consecutive, we can't use the count as they are. We still need to find out how many plant we can plant for the consecutive slots.

Greedy algorithm approach

    The last way to solve the problem is to use a greedy algorithm. We try to plant the flower in the first available empty slot and continue to plant until there are no more available plots.
Surprisingly, this approach works in this case without causing the problem (draw it on the paper to see if it is true.)

This makes the code simpler than the previous approach with the same time complexity $O(N)$.


Here is the complete code for the greedy algorithm.

	#include<iostream>
	using namespace std;
	//greedy algorithm
	bool plant_flower(int* input, int len, int target)
	{
	int count = 0;
	for (int i = 0; i<len; i++)
	{
	if (input[i] == 1)
	continue;
	if (i > 0 && input[i-1] == 1)
	continue;
	if (i< len-1 && input[i+1] == 1)
	continue;
	count++;
	input[i] = 1;
	}
	return count >= target;
	}
	int main()
	{
	int input1 [9] = {1,0,0,0,0,0,1,0,0 };
	int input2 [9] = {1,0,0,0,0,0,1,0,0 };
	int input3 [9] = {1,0,0,1,0,0,1,0,0 };
	int input4 [9] = {1,0,0,1,0,0,1,0,0 };
	int input5 [1] = {0};
	int input6 [1] = {0};
	cout <<"{1,0,0,0,0,0,1,0,0 }, count = 3 => "<<plant_flower(input1, 9, 3)<<endl;
	cout <<"{1,0,0,0,0,0,1,0,0 }, count = 4 => "<<plant_flower(input2, 9, 4)<<endl;
	cout <<"{1,0,0,1,0,0,1,0,0 }, count = 1 => "<<plant_flower(input3, 9, 1)<<endl;
	cout <<"{1,0,0,1,0,0,1,0,0 }, count = 2 => "<<plant_flower(input4, 9, 2)<<endl;
	cout <<"{0}, count = 1 => "<<plant_flower(input5, 1, 1)<<endl;
	cout <<"{0}, count = 2 => "<<plant_flower(input6, 1, 2)<<endl;
	return 1;
	}

view raw plant_flower_greedy.cpp hosted with ❤ by GitHub

Here is the code for the linear search with preprocessing

	include<vector>
	#include<iostream>
	#include<math.h>
	using namespace std;
	bool plant_flower(int * bed, int len, int sum)
	{
	vector<int> cluster;
	int cur, i =0;
	int prev = INT_MIN;
	for(i = 0; i < len; i++)
	{
	cur = bed[i];
	if (cur == 1)
	{
	if (i > 0 )
	bed[i-1] = 1;
	} else if (cur == 0 && prev == 1)
	{
	bed[i] = 1;
	}
	prev = cur;
	}
	int count = 0;
	for(i = 0; i < len; i++)
	{
	if (bed[i] == 0)
	count++;
	else if (count > 0)
	{
	cluster.push_back(count);
	count = 0;
	}
	if (i == len-1)
	cluster.push_back(count);
	}
	for (i = 0; i<cluster.size(); i++)
	{
	sum -= ceil( (double)cluster[i]/(double)2);
	}
	return sum <= 0;
	}
	int main()
	{
	int input1 [9] = {1,0,0,0,0,0,1,0,0 };
	int input2 [9] = {1,0,0,0,0,0,1,0,0 };
	int input3 [9] = {1,0,0,1,0,0,1,0,0 };
	int input4 [9] = {1,0,0,1,0,0,1,0,0 };
	int input5 [1] = {0};
	int input6 [1] = {0};
	cout <<"{1,0,0,0,0,0,1,0,0 }, count = 3 => "<<plant_flower(input1, 9, 3)<<endl;
	cout <<"{1,0,0,0,0,0,1,0,0 }, count = 4 => "<<plant_flower(input2, 9, 4)<<endl;
	cout <<"{1,0,0,1,0,0,1,0,0 }, count = 1 => "<<plant_flower(input3, 9, 1)<<endl;
	cout <<"{1,0,0,1,0,0,1,0,0 }, count = 2 => "<<plant_flower(input4, 9, 2)<<endl;
	cout <<"{0}, count = 1 => "<<plant_flower(input5, 1, 1)<<endl;
	cout <<"{0}, count = 2 => "<<plant_flower(input6, 1, 2)<<endl;
	return 1;
	}

view raw plant_flower.cpp hosted with ❤ by GitHub

UPDATE (2022-06-28): Solved the problem with the brute-force DFS. It is not optimal. 

	'''
	planting pots
	general approach.
	DFS with backtracking
	search(pots, left, next_pos)
	18:45: for algorithm and write up the code. O(N!)
	can do with dynamic progrogramming
	'''
	# code
	def search(pots, left, next):
	if next >= len(pots): # reach the end of pots
	if left == 0:
	return True
	return False
	for i in range(next, len(pots)):
	# check if we can plant
	if pots[i] != 1 and (i == 0 or pots[i-1] != 1) and (i == len(pots) - 1 or pots[i+1]!= 1):
	# plant and search more
	pots[i] = 1
	left -= 1
	result = search(pots, left, i + 1)
	if result == True:
	return result
	# backtrack
	pots[i] = 0
	left += 1
	return False
	def can_pot(pots, target):
	return search(pots, target, 0)
	# test
	input=[1,0,0,0,0,0,1,0,0]
	target = 3
	result = can_pot(input, target)
	print("can pod {} plants in this pots -> {}? {}".format(target, input, result))
	target = 4
	result = can_pot(input, target)
	print("can pod {} plants in this pots -> {}? {}".format(target, input, result))
	input =[1,0,0,1,0,0,1,0,0 ]
	target = 1
	result = can_pot(input, target)
	print("can pod {} plants in this pots -> {}? {}".format(target, input, result))
	target = 2
	result = can_pot(input, target)
	print("can pod {} plants in this pots -> {}? {}".format(target, input, result))
	input =[0]
	target = 1
	result = can_pot(input, target)
	print("can pod {} plants in this pots -> {}? {}".format(target, input, result))
	target = 2
	result = can_pot(input, target)
	print("can pod {} plants in this pots -> {}? {}".format(target, input, result))

view raw check_if_planting_possible.py hosted with ❤ by GitHub

18:45: for algorithm and bug-free code

I tried to do it with dynamic programming. This can run in $O(N)$ time. Much faster.

	class PlantingPlanner:
	def __init__(self, pots):
	self.v = pots
	self.s = [ 0 for i in range(len(pots))]
	self.find_max_plants()
	def get_s(self, i):
	if i < 0 or i > len(self.s) - 1:
	return 0 # just very large number. or python MIN ?
	return self.s[i]
	def get_lvalue(self, i):
	return 1 if self.v[i] == 0 and (i == 0 or self.v[i -1] == 0) and (i == len(self.v) -1 or self.v[i +1] == 0) else -1000
	def find_max_plants(self):
	for i in range(len(self.v)): # v = -1000
	value = self.get_lvalue(i)
	self.s[i] = max(self.get_s(i-1), self.get_s(i-2) + value)
	self.max_spots = self.s[-1]
	def can_pot(self, target):
	return target <= self.max_spots
	# test
	input=[1,0,0,0,0,0,1,0,0]
	target = 3
	planner = PlantingPlanner(input)
	result = planner.can_pot(target)
	print("can pod {} plants in this pots -> {}? {}".format(target, input, result))
	target = 4
	result = planner.can_pot(target)
	print("can pod {} plants in this pots -> {}? {}".format(target, input, result))
	input =[1,0,0,1,0,0,1,0,0 ]
	planner = PlantingPlanner(input)
	target = 1
	result = planner.can_pot(target)
	print("can pod {} plants in this pots -> {}? {}".format(target, input, result))
	target = 2
	result = planner.can_pot(target)
	print("can pod {} plants in this pots -> {}? {}".format(target, input, result))
	input =[0]
	planner = PlantingPlanner(input)
	target = 1
	result = planner.can_pot(target)
	print("can pod {} plants in this pots -> {}? {}".format(target, input, result))
	target = 2
	result = planner.can_pot(target)
	print("can pod {} plants in this pots -> {}? {}".format(target, input, result))

view raw check_if_planting_possible_dp.py hosted with ❤ by GitHub

18:00 to write up the code.