## 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. `1 <= N <= 20000`
2. `1 <= bulbs[i] <= N`
3. `bulbs` is a permutation of numbers from `1` to `N`.
4. `0 <= K <= 20000`

## Rust Solution

``````struct Solution;

use std::collections::BTreeSet;

impl Solution {
fn k_empty_slots(bulbs: Vec<i32>, k: i32) -> i32 {
let n = bulbs.len();
let mut set: BTreeSet<i32> = BTreeSet::new();
for i in 0..n {
let day = (i + 1) as i32;
let mid = bulbs[i];
if let Some(left) = set.range(..mid).next_back() {
if mid - left - 1 == k {
return day;
}
}
if let Some(right) = set.range(mid..).next() {
if right - mid - 1 == k {
return day;
}
}
set.insert(mid);
}
-1
}
}

#[test]
fn test() {
let bulbs = vec![1, 3, 2];
let k = 1;
let res = 2;
assert_eq!(Solution::k_empty_slots(bulbs, k), res);
let bulbs = vec![1, 3, 2];
let k = 1;
let res = 2;
assert_eq!(Solution::k_empty_slots(bulbs, k), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.