LeetCode 683 - K Empty Slots

LeetCode Problem 683

Difficulty: 🔴 Hard
Topics: Array, Binary Indexed Tree, Segment Tree, Queue, Sliding Window, Heap (Priority Queue), Ordered Set, Monotonic Queue

Solution

Let's go through a complete, detailed technical solution guide for LeetCode 683 - K Empty Slots following your formatting instructions.

Problem Understanding

The problem asks us to find the earliest day when there are exactly k bulbs turned off between two bulbs that are turned on. You are given an array bulbs where bulbs[i] tells you which bulb (1-indexed) is turned on on day i+1.

Restated, imagine a row of bulbs initially all off. Each day, you turn on one bulb based on the order in the bulbs array. You are tasked with finding the minimum day number such that there exists two on bulbs with exactly k off bulbs in between. If this never happens, return -1.

The input array bulbs is a permutation of numbers 1 to n. This guarantees there are no duplicates and every bulb eventually turns on. The array size n can be up to 2 * 10^4, which is too large for naive brute-force simulations that check every pair of bulbs each day.

Important edge cases include:

k = 0, where we need adjacent bulbs turned on.
Bulbs turning on in ascending or descending order, which may never produce a valid gap.
Maximum allowed input size (n = 2 * 10^4) which requires an efficient solution.

Approaches

Brute Force

The naive approach is to simulate the bulb array day by day. On each day, after turning on the current bulb, check every possible pair of turned-on bulbs to see if the number of off bulbs between them is exactly k. This would involve a nested loop: for each day, scanning the array to find turned-on bulbs and counting gaps.

While correct, this is too slow because for n bulbs, each day could take up to O(n) to check all pairs. Total complexity could reach O(n^2) or worse, which is unacceptable for n = 2 * 10^4.

Optimal Approach

The key insight is that we do not need to check all pairs each day. Instead, we can transform the problem using an array days where days[i] is the day the i-th bulb (1-indexed) turns on.

Then, finding two on bulbs with exactly k off bulbs between them becomes a window problem. For each window of size k+2 (start at left and right = left + k + 1), the bulbs inside the window must all turn on after the left and right bulbs.

We can implement this efficiently using a sliding window:

Transform bulbs into a days array.
Iterate over all possible left positions and maintain a sliding window of size k+2.
If all bulbs inside the window are turned on later than the edges, update the minimum day.

This reduces the problem from O(n^2) to O(n) time with O(n) space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Simulate day by day, check all pairs of on bulbs
Sliding Window (Optimal)	O(n)	O(n)	Transform to days array, check windows of size k+2 efficiently

Algorithm Walkthrough

Create a days array of length n where days[i] represents the day the i+1-th bulb turns on. Iterate over bulbs to fill it: days[bulb-1] = day_index + 1.
Initialize res = infinity to store the earliest day satisfying the condition.
Set left = 0 and right = k + 1. These are the indices of potential "edges" of the gap.
Slide a window from left to the end of the days array:
For each bulb inside the window (left+1 to right-1), check if it turns on before either edge (days[left] or days[right]). If yes, move left to this bulb and reset right = left + k + 1.
If the window is valid (all inner bulbs turn on later than edges), update res with max(days[left], days[right]).
Move left by 1 and update right = left + k + 1.
If res is still infinity after the loop, return -1. Otherwise, return res.

Why it works: The days array encodes the exact day each bulb turns on. By checking windows of size k+2, we directly enforce the condition that there are exactly k bulbs turned off between two on bulbs. Inner bulbs turning on later ensures the gap is empty at that day.

Python Solution

from typing import List

class Solution:
    def kEmptySlots(self, bulbs: List[int], k: int) -> int:
        n = len(bulbs)
        days = [0] * n
        for day, bulb in enumerate(bulbs):
            days[bulb - 1] = day + 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 = right
                right = left + k + 1

        return -1 if res == float('inf') else res

This implementation first creates the days array, which lets us convert the problem from dynamic day-by-day simulation to a static window check. The sliding window loop ensures that we efficiently check only valid candidate windows. Moving left to the violating bulb ensures we never revisit invalid windows.

Go Solution

func kEmptySlots(bulbs []int, k int) int {
    n := len(bulbs)
    days := make([]int, n)
    for day, bulb := range bulbs {
        days[bulb-1] = day + 1
    }

    res := n + 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 days[left] > days[right] {
                if days[left] < res {
                    res = days[left]
                }
            } else {
                if days[right] < res {
                    res = days[right]
                }
            }
            left = right
            right = left + k + 1
        }
    }

    if res == n+1 {
        return -1
    }
    return res
}

In Go, slices and indexing behave similarly to Python lists. The main difference is initializing res to n+1 instead of infinity. Loops and comparisons are otherwise identical.

Worked Examples

Example 1: bulbs = [1,3,2], k = 1

Step-by-step:

days = [1, 3, 2]
Start window left=0, right=2
Check inner bulbs between left and right (i=1): days[1]=3, days[left]=1, days[right]=2. days[i] > days[left] and days[i] > days[right]? No, 3 > 1 and 3 > 2 valid.
Update res = max(days[left], days[right]) = max(1, 2) = 2

Return 2.

Example 2: bulbs = [1,2,3], k = 1

days = [1, 2, 3]
Window left=0, right=2
Inner bulb i=1, days[i]=2 < days[right]=3? Yes → window invalid. Move left=1, right=3 (out of bounds)

Return -1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We slide a window across `days` with each inner bulb checked at most once
Space	O(n)	Extra `days` array of size `n`

The algorithm is linear because each bulb is considered as a window edge at most once. The sliding window ensures no nested full scans.

Test Cases

# Provided examples
assert Solution().kEmptySlots([1,3,2], 1) == 2  # Two on bulbs with 1 off between
assert Solution().kEmptySlots([1,2,3],