leetcode 683 - K Empty Slots

https://leetcode.com/problems/k-empty-slots/
https://leetcode.com/articles/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[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.
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//O(N*LogN)
class Solution {
public:
int kEmptySlots(vector<int>& bulbs, int K) {
set<int> s;

for (int i = 0; i < bulbs.size(); i++) {
s.insert(bulbs[i]);

auto it = s.find(bulbs[i]);
if (it != s.begin()) {
if (*it - *prev(it) == K + 1)
return i + 1;
}
if (next(it) != s.end()) {
if (*next(it) - *it == K + 1)
return i + 1;
}
}

return -1;
}
};

/*
O(N)
*/
class Solution {
public:
int kEmptySlots(vector<int>& bulbs, int K) {
int n = bulbs.size();
vector<int> days(n);

for (int i = 0; i < n; i++) {
days[bulbs[i] - 1] = i + 1;
}

int ans = INT_MAX;

int i = 0, j = K + 1;

while (j < n) {
bool ok = true;
for (int p = i + 1; p < j; p++) {
if (days[p] < days[i] || days[p] < days[j]) {
ok = false;
i = i + 1;
j = i + K + 1;
break;
}
}

if (ok) {
ans = min(ans, max(days[i], days[j]));
i = j;
j = i + K + 1;
}
}

return ans == INT_MAX ? -1 : ans;
}
};