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 (Days Array)

Intuition

Track the day each bulb is turned on. For each window of size k+2, check if the bulbs at the ends are on before any in the middle.

Approach

  1. Create an array days where days[i] is the day bulb i+1 is turned on.
  2. For each window of size k+2, check if all bulbs between the ends are turned on after both ends.
  3. Return the earliest day found, or -1 if none.

Code

Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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 res = Integer.MAX_VALUE, left = 0, right = k + 1;
        for (; right < n; ++left, ++right) {
            boolean valid = true;
            for (int i = left + 1; i < right; ++i) {
                if (days[i] < days[left] || days[i] < days[right]) {
                    left = i - 1;
                    right = left + k + 1;
                    valid = false;
                    break;
                }
            }
            if (valid) res = Math.min(res, Math.max(days[left], days[right]));
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def kEmptySlots(bulbs, k):
    n = len(bulbs)
    days = [0] * n
    for i, b in enumerate(bulbs):
        days[b - 1] = i + 1
    res = 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:
            res = min(res, max(days[left], days[right]))
            left += 1
            right += 1
    return -1 if res == float('inf') else res

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)