Given an integer array plots[] containing 0s and 1s, where plots[i] = 0 means ith plot is empty and plots[i] = 1 means ith plot is planted with flower. The task is to check if N new flowers can be planted in empty plots such that no two flowers are adjacent.

Examples:

Input: plots[] = {1, 0, 0, 0, 1}, N = 1
Output: True
Explanation: You can plant flowers at positions 2 without violating the no-adjacent-flowers rule.

Input:  plots[] = {1, 0, 0, 0, 1}, N = 2
Output: False
Explanation: You cannot plant flowers 2 without violating the no-adjacent-flowers rule.

Approach: To solve the problem, follow the below idea:

The problem can be solved by iterating through the plots and check for empty plots where a new flower can be planted. For each empty plot, we check if the plot before and after it are also empty or out of bounds (if the plot is at the ends). We keep a count of how many flowers we can plant as we go through the plots. If the count reaches or exceeds N, we return true. If we finish iterating through the plots and the count is less than N, we return false.

Step-by-step algorithm:

• Initialize a counter to keep track of the number of flowers that can be planted.
• Iterate through the plots array.
• For each plot, check if it is empty (plots[i] == 0).
• If it is empty, check if the previous plot (i-1) is empty or out of bounds, and the next plot (i+1) is empty or out of bounds.
• If both conditions are met, plant a flower at this plot by setting plots[i] to 1 and increment the counter.
• If the counter reaches N, return true.
• Continue iterating through the plots.
• If the loop completes and the counter is still less than N, return false.

Below is the implementation of the algorithm:

#include <bits/stdc++.h>
using namespace std;

// Function to check if n new flowers can be planted in the
// plots
bool canPlaceFlowers(vector<int>& plots, int N)
{
    int count = 0;
    int size = plots.size();

    for (int i = 0; i < size; ++i) {
        // Check if the current plot is empty
        if (plots[i] == 0) {
            // Check the previous and next plots
            bool emptyPrev
                = (i == 0) || (plots[i - 1] == 0);
            bool emptyNext
                = (i == size - 1) || (plots[i + 1] == 0);

            // If both previous and next plots are empty or
            // out of bounds
            if (emptyPrev && emptyNext) {
                // Plant a flower
                plots[i] = 1;
                ++count;

                // If the required number of flowers have
                // been planted, return true
                if (count >= N)
                    return true;
            }
        }
    }

    // If not enough flowers could be planted, return false
    return count >= N;
}

int main()
{
    // Test case 1
    vector<int> plots = { 1, 0, 0, 0, 1 };
    int N = 2;
    cout << (canPlaceFlowers(plots, N) ? "True" : "False" )<< endl;
}

False

Time Complexity: O(M), where M is the length of the plots array
Auxiliary Space: O(1)