Greedy: Plant n flowers in flower bed

Problem Statement:

You are given array that represents flowerbed, where some plants are placed. You are also given new flowers to be placed.

You need to place the flowers in such a way that they should not be placed adjacent.

You need to return true or false based on if the “n” new flowers can be placed or not.

1 means already flower has been planted.

0 means the place is empty.

Example

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

Solution

We can solve this approach by greedy method.

we will place a flower at every empty slot encountered from left to right.

In below code i have explained with example.

Solution in C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;

bool can_place_flowers(vector<int>& flowerbed, int n) 
{
  int count = 0;

  for(int i = 0; i < flowerbed.size() && count < n; i++) 
  {
      // if the flower bed has an empty slot   
      if(flowerbed[i] == 0) 
      {

      // check if there are 3 empty slots available.
      // get next and prev flower bed slot values. 
      // If i lies at the ends the next and prev are considered as 0. 

         int next = (i == flowerbed.size() - 1) ? 0 : flowerbed[i + 1]; 
         int prev = (i == 0) ? 0 : flowerbed[i - 1];
         if(next == 0 && prev == 0) 
         {
             flowerbed[i] = 1;
             count++;
         }
      }
  }
  
  return count == n;
}


int main()
{
   vector<int> flowerbed = {1, 0, 0, 0, 1};
   int n =1;
   

   if(can_place_flowers(flowerbed, n)){
      cout<<"Yes, new flowers can be placed"<<endl;
   } else {
      cout<<"No, new flowers cannot be placed"<<endl;

   }
   return 0;
}

Output:

Yes, new flowers can be placed