683. K Empty Slots

There is a garden withNslots. In each slot, there is a flower. TheNflowers will bloom one by one inNdays. In each day, there will beexactlyone flower blooming and it will be in the status of blooming since then.

Given an arrayflowersconsists of number from1toN. Each number in the array represents the place where the flower will open in that day.

For example,flowers[i] = xmeans that the unique flower that blooms at dayiwill be at positionx, whereiandxwill be in the range from1toN.

Also given an integerk, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them iskand 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].

Additional Notes:

flowers[i] = x

1. should mean that the unique flower that blooms at dayi+1(noti) will be at positionx.

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;
    }
};