Find Latest Day of Blossoming Group of Size K in a Permutation Array P

Given a zero-indexed array P containing N integers (a permutation of number from 1 to N), where P[i] denotes the number of the rose which will start blooming on day number i+1, and integer K, return the latest day on which there is some blossoming group of size K. If there is no such day function should return -1.

Examples:

Input : P=[3,1,5,4,2],  K=2
Output : -1
Means,
3rd rose blooms on Day 1
1st rose blooms on Day 2
5th rose blooms on Day 3
4th rose blooms on Day 4
2nd rose blooms on Day 5

Explaination :
Day1: - - R - -       -> one group [3]
Day2: R - R - -       -> two group [1], [3]
Day3: R - R - R       -> three group [1], [3], [5]
Day4: R - R R R       -> two group [1], [3,4,5]
Day5: R R R R R       -> one group [1,2,3,4,5]
Rose: 1 2 3 4 5 

Input : P=[3,1,5,4,2] ,  K=1
Output : 4

Approach :
The idea is that we maintain an {int,int} pair in each interval point (that gives the first and last position of the block that contains that point), but since we will need only the endpoints of a consecutive block we update only the endpoints.

Count the number of blocks that has length = K. What happens when a new rose bushes at “rose”?
If there is a bush already at rose-1 then check if we destroyed a block = K or not, the same is true for rose+1. (note that these two blocks should be distinct if they exist, because at “rose” there was no bush). Then examine the new block length=end-start+1 if it is equal to K or not.

Below is the implementation of the above approach:

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

int garden(vector<int>& P, int K) {
    int ans = -1;
    int n = P.size();
    int count = 0;

    vector<pair<int, int>> S(n + 2, {-1, -1});

    for (int i = 0; i < n; i++) {
        int rose = P[i];

        int start = (S[rose - 1].first == -1 ? rose : S[rose - 1].first);
        int end = (S[rose + 1].second == -1 ? rose : S[rose + 1].second);

        if (end - start + 1 == K) count++;
        if (rose - start == K) count--;
        if (end - rose == K) count--;

        if (count > 0) ans = i + 1;

        S[start].second = end;
        S[end].first = start;
    }
    return ans;
}

// Driver function
int main(int argc, char* argv[]) {
    vector<int> vec = {3, 1, 5, 4, 2};
    int k = 1;
    int ans;
    ans = garden(vec, k);
    cout << ans << endl;
    return 0;
}

Output :-

Time Complexity :- O(n)
Space Complexity :- O(n)