K Empty Slots

K Empty Slots

1. What is this problem about?

The K Empty Slots interview question is an interval and timing problem. You have $N$ bulbs in a row. Each day, one bulb is turned on according to a given sequence. You need to find the earliest day on which there exist two turned-on bulbs that are exactly k positions apart, such that all bulbs between them are currently off.

2. Why is this asked in interviews?

Google uses the K Empty Slots coding problem to evaluate a candidate's ability to handle Sliding Window and Ordered Set logic. It requires you to track neighbors in a dynamic set (which bulbs are on) and check distances. It evaluations your proficiency with Segment Trees or Binary Indexed Trees if you choose a query-based approach.

3. Algorithmic pattern used

This problem can be solved using a Sliding Window on the "Days" array.

1. Days Array: Create an array days where days[i] is the day the bulb at position i is turned on.
2. The Condition: We are looking for a range [i, i + k + 1] such that days[i] and days[i + k + 1] are both less than all days[j] for $j$ in the middle.
3. Sliding Window: Move a window of size $k+1$. If any element inside the window is smaller than both boundaries, the window is invalid. Move the window to start at that smaller element.
4. Alternative: Use an Ordered Set (like TreeSet) to store positions of turned-on bulbs. For each new bulb, check its successor and predecessor in the set.

4. Example explanation

Bulbs: [1, 3, 2], $k = 1$.

• Day 1: Bulb 1 is on. set = {1}.
• Day 2: Bulb 3 is on. set = {1, 3}.
  • Check distance between 1 and 3: $|3 - 1| = 2$.
  • Number of empty slots is $2 - 1 = 1$. This matches $k=1$.
• Result: Day 2.

5. Common mistakes candidates make

• Linear Scan per Day: Checking the whole row of bulbs every day ($O(N^2)$), which will time out.
• Incorrect distance math: Miscalculating "k empty slots" as a distance of $k$ instead of $k+1$.
• Ignoring the "Earliest" rule: Not returning the minimum day if multiple valid gaps occur.

6. Interview preparation tip

Master the Sliding Window Minimum/Maximum pattern. Being able to check if all values in a range are greater than some threshold in $O(1)$ or $O(\log N)$ is a critical skill for high-level Array interview patterns.