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:

1
2
3
4
5
6
7

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:

1
2

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

Constraints:

  • n == bulbs.length
  • 1 <= n <= 2 * 10^4
  • 1 <= bulbs[i] <= n
  • bulbs is a permutation of numbers from 1 to n.
  • 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

  1. Create an array days where days[i] is the day the bulb at position i+1 is turned on.
  2. Use a sliding window of size k+2 to 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.
  3. Return the minimum such day, or -1 if none exists.

Code

 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

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;
    }
};
 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

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 } }
 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

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;
    }
}
 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

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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
 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

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 }
}
 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

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.