K Empty Slots
HardUpdated: Aug 2, 2025
Practice on:
Problem
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)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, return theminimum 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.
Examples
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
Constraints:
n == bulbs.length1 <= n <= 2 * 10^41 <= bulbs[i] <= nbulbsis a permutation of numbers from1ton.0 <= k <= 2 * 10^4
Solution
Method 1 – Sliding Window with Ordered Set
Intuition
We want to find the earliest day when there are exactly k bulbs off between two bulbs that are on, and no other bulbs in between are on. By simulating the process and maintaining the positions of bulbs that are on in an ordered set, we can efficiently check the required condition for each day.
Approach
- Create an array
dayswheredays[i]is the day the bulb at positioni+1is turned on. - Use a sliding window of size
k+2to check for valid intervals:- For each window, check if all bulbs between the ends are turned on after both ends.
- If so, record the maximum of the two end days as a candidate answer.
- Return the minimum such day, or -1 if none exists.
Code
C++
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 left = 0, right = k + 1;
while (right < n) {
bool valid = true;
for (int i = left + 1; i < right; ++i) {
if (days[i] < days[left] || days[i] < days[right]) {
left = i;
right = left + k + 1;
valid = false;
break;
}
}
if (valid) {
ans = min(ans, max(days[left], days[right]));
left = right;
right = left + k + 1;
}
}
return ans == INT_MAX ? -1 : ans;
}
};
Go
func kEmptySlots(bulbs []int, k int) int {
n := len(bulbs)
days := make([]int, n)
for i, b := range bulbs {
days[b-1] = i + 1
}
ans := 1<<31 - 1
left, right := 0, k+1
for right < n {
valid := true
for i := left + 1; i < right; i++ {
if days[i] < days[left] || days[i] < days[right] {
left = i
right = left + k + 1
valid = false
break
}
}
if valid {
if max(days[left], days[right]) < ans {
ans = max(days[left], days[right])
}
left = right
right = left + k + 1
}
}
if ans == 1<<31-1 {
return -1
}
return ans
}
func max(a, b int) int { if a > b { return a } else { return b } }
Java
class Solution {
public int kEmptySlots(int[] bulbs, int k) {
int n = bulbs.length;
int[] days = new int[n];
for (int i = 0; i < n; ++i) days[bulbs[i] - 1] = i + 1;
int ans = Integer.MAX_VALUE;
int left = 0, right = k + 1;
while (right < n) {
boolean valid = true;
for (int i = left + 1; i < right; ++i) {
if (days[i] < days[left] || days[i] < days[right]) {
left = i;
right = left + k + 1;
valid = false;
break;
}
}
if (valid) {
ans = Math.min(ans, Math.max(days[left], days[right]));
left = right;
right = left + k + 1;
}
}
return ans == Integer.MAX_VALUE ? -1 : ans;
}
}
Kotlin
class Solution {
fun kEmptySlots(bulbs: IntArray, k: Int): Int {
val n = bulbs.size
val days = IntArray(n)
for (i in bulbs.indices) days[bulbs[i] - 1] = i + 1
var ans = Int.MAX_VALUE
var left = 0
var right = k + 1
while (right < n) {
var valid = true
for (i in left + 1 until right) {
if (days[i] < days[left] || days[i] < days[right]) {
left = i
right = left + k + 1
valid = false
break
}
}
if (valid) {
ans = minOf(ans, maxOf(days[left], days[right]))
left = right
right = left + k + 1
}
}
return if (ans == Int.MAX_VALUE) -1 else ans
}
}
Python
def k_empty_slots(bulbs: list[int], k: int) -> int:
n = len(bulbs)
days = [0] * n
for i, b in enumerate(bulbs):
days[b-1] = i + 1
ans = float('inf')
left, right = 0, k + 1
while right < n:
valid = True
for i in range(left + 1, right):
if days[i] < days[left] or days[i] < days[right]:
left = i
right = left + k + 1
valid = False
break
if valid:
ans = min(ans, max(days[left], days[right]))
left = right
right = left + k + 1
return -1 if ans == float('inf') else ans
Rust
fn k_empty_slots(bulbs: Vec<i32>, k: i32) -> i32 {
let n = bulbs.len();
let mut days = vec![0; n];
for (i, &b) in bulbs.iter().enumerate() {
days[b as usize - 1] = i as i32 + 1;
}
let mut ans = i32::MAX;
let (mut left, mut right) = (0, k + 1);
while (right as usize) < n {
let mut valid = true;
for i in (left + 1)..right {
if days[i as usize] < days[left as usize] || days[i as usize] < days[right as usize] {
left = i;
right = left + k + 1;
valid = false;
break;
}
}
if valid {
ans = ans.min(days[left as usize].max(days[right as usize]));
left = right;
right = left + k + 1;
}
}
if ans == i32::MAX { -1 } else { ans }
}
TypeScript
class Solution {
kEmptySlots(bulbs: number[], k: number): number {
const n = bulbs.length;
const days = Array(n);
for (let i = 0; i < n; ++i) days[bulbs[i] - 1] = i + 1;
let ans = Infinity;
let left = 0, right = k + 1;
while (right < n) {
let valid = true;
for (let i = left + 1; i < right; ++i) {
if (days[i] < days[left] || days[i] < days[right]) {
left = i;
right = left + k + 1;
valid = false;
break;
}
}
if (valid) {
ans = Math.min(ans, Math.max(days[left], days[right]));
left = right;
right = left + k + 1;
}
}
return ans === Infinity ? -1 : ans;
}
}
Complexity
- ⏰ Time complexity:
O(n)— Each bulb is checked at most twice. - 🧺 Space complexity:
O(n)— For the days array.