This page explains Java solution to problem `K Empty Slots`

using `TreeSet`

data structure.

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 every day 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)`

day, we will turn on the bulb at position ^{th}`x`

where `i`

is `0-indexed`

and `x`

is `1-indexed`

.

Given an integer `k`

, return 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`

.

Input: bulbs = [1,3,2], k = 1Output: 2Explanation:

On the first day: bulbs[0] = 1, first bulb is turned on: [1,0,0]

On the second day: bulbs[1] = 3, third bulb is turned on: [1,0,1]

On the third day: bulbs[2] = 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.

Input: bulbs = [1,2,3], k = 1Output: -1

```
package com.vc.hard;
import java.util.*;
class KEmptySlots {
public int kEmptySlots(int[] bulbs, int k) {
TreeSet<Integer> bulbSet = new TreeSet<>();
for(int day = 0; day < bulbs.length; day++) {
int bulbPosition = bulbs[day];
Integer prevBulbPosition = bulbSet.lower(bulbPosition);
Integer nextBulbPosition = bulbSet.higher(bulbPosition);
if((prevBulbPosition != null && bulbPosition - prevBulbPosition - 1 == k) ||
(nextBulbPosition != null && nextBulbPosition - bulbPosition - 1 == k)) {
return day + 1;
}
bulbSet.add(bulbPosition);
}
return -1;
}
}
```

O(N * log N) Where

N is total number of bulbs in an input array.

O(N) Where

N is total number of bulbs in an input array.