# 683. K Empty Slots

You have N bulbs in a row numbered from 1 to N. Initially, all the bulbs are turned off. We turn on exactly one bulb everyday until all bulbs are on after N days.

You are given an array bulbs of length N where bulbs[i] = x means that on the (i+1)th day, we will turn on the bulb at position x where i is 0-indexed and x is 1-indexed.

Given an integer K, find out the minimum day number such that there exists two turned on bulbs that have exactly K bulbs between them that are all turned off.

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

Example 1:

Input:
bulbs: [1,3,2]
K: 1
Output: 2
Explanation:
On the first day: bulbs = 1, first bulb is turned on: [1,0,0]
On the second day: bulbs = 3, third bulb is turned on: [1,0,1]
On the third day: bulbs = 2, second bulb is turned on: [1,1,1]
We return 2 because on the second day, there were two on bulbs with one off bulb between them.
Example 2:

Input:
bulbs: [1,2,3]
K: 1
Output: -1

Note:

1 <= N <= 20000
1 <= bulbs[i] <= N
bulbs is a permutation of numbers from 1 to N.
0 <= K <= 20000

## Solution

1. TreeMap
2. Sliding Window use day[i] represents the day that bulb i+1 is turned on for i belonging to left + 1, left + 2, ... , left + k, it satisfies day[i] > day[left] && day[i] > day[right] ## Complexity
3. O(NlogN) the insertion of TreeMap cost O(logN) O(N)
4. O(N) O(1) ## Code ```java class Solution { public int kEmptySlots(int[] bulbs, int K) { TreeSet<Integer> active = new TreeSet<>(); for(int i=0; i<bulbs.length; i++){ active.add(bulbs[i]); Integer lower = active.lower(bulbs[i]); if(lower != null && bulbs[i] - lower == K+1) return i+1; Integer higher = active.higher(bulbs[i]); if(higher != null && higher - bulbs[i] == K+1) return i+1; } return -1; } } ```
``````class Solution {
public int kEmptySlots(int[] flowers, int k) {

int res = Integer.MAX_VALUE;
int[] day = new int[flowers.length + 1];
for (int i = 0; i < flowers.length; i ++) {
// day[i] is the day when the flower at position i blooms
// day is useless here
day[flowers[i]] = i+1;
}

// we now are supposed to find a subarray of day[left, right] where its length is k+2
// and all i that left < i < right, we have day[i] > day[left] and day[i] > day[right]
int left = 1, right = k + 2;
for (int i = 2; right < day.length; i++) {
if (i == right) {
// found a sub array
res = Math.min(res, Math.max(day[left], day[right]));
left = i;
right = left + k + 1;
} else if (day[i] < day[left] || day[i] < day[right]) {
left = i;
right = left + k + 1;
}
}

return (res == Integer.MAX_VALUE)?-1:res;
}

}
``````