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 :-
4
Time Complexity :- O(n)
Space Complexity :- O(n)