683. K Empty Slot

Description

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].

Note

Method 1: O(n*k)

f[i] = x means blooms at day i is at position x.

g[x] = i means blooms at position x is on day i.

So, if the position between x to x+k, has bloom day i are not between g[x], g[x2], them it is a good solution.

Method 2:

again, validate the range from g[x] -> g[x + k + 1]. But, consider the moving window.

Code

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, res = INT_MAX;
    for(int i = 0; right < days.size(); i++){
        if(days[i] < days[left] || days[i] <= days[right]){   
            if(i == right)res = min(res, max(days[left], days[right]));    //we get a valid subarray
            left = i, right = k + 1 + i;
        }
    }
    return (res == INT_MAX)?-1:res;
}