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