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

b'
\n

#### Approach #1: Insert Into Sorted Structure [Accepted]

\n

Intuition

\n

Let\'s add flowers in the order they bloom. When each flower blooms, we check it\'s neighbors to see if they can satisfy the condition with the current flower.

\n

Algorithm

\n

We\'ll maintain `active`, a sorted data structure containing every flower that has currently bloomed. When we add a flower to `active`, we should check it\'s lower and higher neighbors. If some neighbor satisfies the condition, we know the condition occurred first on this day.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity (Java): , where is the length of `flowers`. Every insertion and search is .

\n
• \n
• \n

Time Complexity (Python): . As above, except `list.insert` is .

\n
• \n
• \n

Space Complexity: , the size of `active`.

\n
• \n
\n
\n

#### Approach #2: Min Queue [Accepted]

\n

Intuition

\n

For each contiguous block ("window") of `k` positions in the flower bed, we know it satisfies the condition in the problem statement if the minimum blooming date of this window is larger than the blooming date of the left and right neighbors.

\n

Because these windows overlap, we can calculate these minimum queries more efficiently using a sliding window structure.

\n

Algorithm

\n

Let `days[x] = i` be the time that the flower at position `x` blooms. For each window of `k` days, let\'s query the minimum of this window in (amortized) constant time using a `MinQueue`, a data structure built just for this task. If this minimum is larger than it\'s two neighbors, then we know this is a place where "`k` empty slots" occurs, and we record this candidate answer.

\n

To operate a `MinQueue`, the key invariant is that `mins` will be an increasing list of candidate answers to the query `MinQueue.min`.

\n

For example, if our queue is `[1, 3, 6, 2, 4, 8]`, then `mins` will be `[1, 2, 4, 8]`. As we `MinQueue.popleft`, `mins` will become `[2, 4, 8]`, then after 3 more `popleft`\'s will become `[4, 8]`, then after 1 more `popleft` will become ``.

\n

As we `MinQueue.append`, we should maintain this invariant. We do it by popping any elements larger than the one we are inserting. For example, if we appended `5` to `[1, 3, 6, 2, 4, 8]`, then `mins` which was `[1, 2, 4, 8]` becomes `[1, 2, 4, 5]`.

\n

Note that we used a simpler variant of `MinQueue` that requires every inserted element to be unique to ensure correctness. Also, the operations are amortized constant time because every element will be inserted and removed exactly once from each queue.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where is the length of `flowers`. In enumerating through the outer loop, we do constant work as `MinQueue.popleft` and `MinQueue.min` operations are (amortized) constant time.

\n
• \n
• \n

Space Complexity: , the size of our `window`.

\n
• \n
\n
\n

#### Approach #3: Sliding Window [Accepted]

\n

Intuition

\n

As in Approach #2, we have `days[x] = i` for the time that the flower at position `x` blooms. We wanted to find candidate intervals `[left, right]` where `days[left], days[right]` are the two smallest values in `[days[left], days[left+1], ..., days[right]]`, and `right - left = k + 1`.

\n

Notice that these candidate intervals cannot intersect: for example, if the candidate intervals are `[left1, right1]` and `[left2, right2]` with `left1 < left2 < right1 < right2`, then for the first interval to be a candidate, `days[left2] > days[right1]`; and for the second interval to be a candidate, `days[right1] > days[left2]`, a contradiction.

\n

That means whenever whether some interval can be a candidate and it fails first at `i`, indices `j < i` can\'t be the start of a candidate interval. This motivates a sliding window approach.

\n

Algorithm

\n

As in Approach #2, we construct `days`.

\n

Then, for each interval `[left, right]` (starting with the first available one), we\'ll check whether it is a candidate: whether `days[i] > days[left]` and `days[i] > days[right]` for `left < i < right`.

\n

If we fail, then we\'ve found some new minimum `days[i]` and we should check the new interval `[i, i+k+1]`. If we succeed, then it\'s a candidate answer, and we\'ll check the new interval `[right, right+k+1]`.

\n\n

Complexity Analysis

\n
\n
• Time and Space Complexity: . The analysis is the same as in Approach #2.
• \n
\n
\n

Analysis written by: @awice. Approach #1 inspired by @StefanPochmann. Approach #3 inspired by @Vincent Cai.

\n
'