683. K Empty Slots

There is a garden with`N`slots. In each slot, there is a flower. The`N`flowers will bloom one by one in`N`days. In each day, there will be`exactly`one flower blooming and it will be in the status of blooming since then.

Given an array`flowers`consists of number from`1`to`N`. Each number in the array represents the place where the flower will open in that day.

For example,`flowers[i] = x`means that the unique flower that blooms at day`i`will be at position`x`, where`i`and`x`will be in the range from`1`to`N`.

Also given an integer`k`, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is`k`and these flowers are not blooming.

If there isn't such day, output -1.

Example 1:

``````Input:

flowers: [1,3,2]
k: 1

Output:
2

Explanation:
In the second day, the first and the third flower have become blooming.
``````

Example 2:

``````Input:

flowers: [1,2,3]
k: 1

Output:
-1
``````

Note:

1. The given array will be in the range [1, 20000].

`flowers[i] = x`

1. should mean that the unique flower that blooms at day`i+1`(not`i`) will be at position`x`.
2. If you can get multiple possible results, then you need to return the minimum one.

Thoughts:

1. construct a reverse index array: days[x] = i + 1 => the blooming day for place "x + 1" .
2. Find the subarray days[left, left + 1, ..., left + k - 1, right] which satisfies for and left + 1<= i <=left + k-1: days[left] < days[i] && days[right] < days[i] => result is max(days[left], day[right]).

Code Time Complexity: O(n), Space Complexity O(n)

``````class Solution {
public:
int kEmptySlots(vector<int>& flowers, int k) {
vector<int> days(flowers.size());
for(int i = 0; i < flowers.size(); i++){
days[flowers[i] - 1] = i + 1;
}
int left = 0 , right = k + 1, ans = INT_MAX;
for (int i = 0; right < days.size(); i++){
if(days[i] < days[left] || days[i] < days[right] || i == right){
if(i == right) ans = min(ans, max(days[right], days[left]));
left = i;
right = i + k + 1;
}
}

return (ans == INT_MAX) ?-1: ans;
}
};
``````