Solution: K Empty Slots

Statement

You are given $n$ bulbs arranged in a row, numbered from $1$ to $n$. Initially, all bulbs are turned off.

Each day, exactly one bulb is switched on. You are given an array, bulbs of length $n$ where bulbs[i] $= x$ means that on day $i + 1$ (1‑indexed), the bulb at position $x$ (also 1‑indexed) is turned on.

So, given an integer k, determine the earliest day (the smallest day number) on which there are two bulbs that are on such that exactly k bulbs are off between them.

If no such day exists, return $-1$.

Constraints:

• $n ==$ bulbs.length

• $1 \leq n \leq 10^3$

• $1 \leq$ bulbs[i] $\leq n$

• bulbs is a permutationIt is a sequence that contains every integer from 1 to n exactly once and in any order. of numbers from $1$ to $n$

• $0 \leq$ k $\leq 10^3$

Solution

The core intuition behind this solution is to avoid simulating bulb states day by day, and instead transform the problem into one of comparing days. The challenge is to find the earliest day when two bulbs are turned on with exactly k bulbs between them, all of which are still off at that time. To do this, the solution creates an array of days where each index represents a bulb’s position, and the value at that index is the day that bulb is turned on.

The solution uses a min heap to keep track of the bulbs in the current window of size k. We iterate through each position in the array of days and add the current day to the min heap, acting as a window. Once the heap contains k elements, we check if the bulbs at the left and right boundaries of the current one ($i -$ k and $i + 1$) were both turned on before the current one. The min heap helps us check this. It always keeps track of the earliest activation day value among the k bulbs in the middle. So, if the earliest day is greater than both days at the left and right boundaries, it means all bulbs in the middle were turned on later, which is exactly what we want.

When we find a valid pair, we return the day the second bulb (among the two ends) was turned on—that’s the day the condition is satisfied. We track the earliest such day across all valid cases and return that as our final result.

Let’s break down the key steps of the solution:

1. We create the days array:

   1. days[i] stores the day the bulb at position i + 1 is turned on.

2. We initialize a variable, result, with len(days) as an upper bound to store the earliest valid day found.

3. We use a min heap, pq, to help track the earliest turn-on day among the k bulbs between any two ends:

   1. As we go through each value (bulb’s day) in the days array, we add it to the min heap.

   2. We keep the size of the heap to k, matching the number of bulbs required to be in between the two ends.

   3. Once we have at least k elements in the heap (i >= k), and we’re not at the last bulb (i < len(days) - 1), we remove the oldest element from the heap to maintain the size.

   4. We then check for a valid pair:

      1. Check the two bulbs at both ends (positions i - k and i + 1) were turned on earlier than the bulbs in between. If yes, then we found a valid day: the max of the two ends is the answer (ans) for this window.

   5. We keep track of the earliest such day of all the valid days in result.

4. If we find at least one valid pair, we return result as the earliest day. Otherwise, return $-1$.

Let’s look at the following illustration to get a better understanding of the solution: