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

``````class Solution {
public:
int kEmptySlots(vector<int>& flowers, int k) {
int res = INT_MAX, left = 0, right = k + 1, n = flowers.size();
vector<int> days(n, 0);
for (int i = 0; i < n; ++i) days[flowers[i] - 1] = i + 1;
for (int i = 0; right < n; ++i) {
if (days[i] < days[left] || days[i] <= days[right]) {
if (i == right) res = min(res, max(days[left], days[right]));
left = i;
right = k + 1 + i;
}
}
return (res == INT_MAX) ? -1 : res;
}
};
``````

``````class Solution {
public:
int kEmptySlots(vector<int>& flowers, int k) {
set<int> s;
for (int i = 0; i < flowers.size(); ++i) {
int cur = flowers[i];
auto it = s.upper_bound(cur);
if (it != s.end() && *it - cur == k + 1) {
return i + 1;
}
it = s.lower_bound(cur);
if (it != s.begin() && cur - *(--it) == k + 1) {
return i + 1;
}
s.insert(cur);
}
return -1;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/683

https://leetcode.com/problems/k-empty-slots/

https://leetcode.com/problems/k-empty-slots/discuss/107931/JavaC%2B%2B-Simple-O(n)-solution

https://leetcode.com/problems/k-empty-slots/discuss/107960/C%2B%2B-ordered-set-Easy-solution

https://leetcode.com/problems/k-empty-slots/discuss/107948/Iterate-over-time-vs.-iterate-over-position

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation