LeetCode 683: K Empty Slots

Problem Restatement

We are given an array bulbs.

There are n bulbs in a row, numbered from 1 to n.

On day i + 1, the bulb at position bulbs[i] turns on.

We need to return the earliest day when there exist two turned-on bulbs with exactly k bulbs between them, and all those k bulbs are still turned off.

If this never happens, return -1. The official statement asks for the minimum day number with two turned-on bulbs that have exactly k off bulbs between them.

Input and Output

Example function shape:

def kEmptySlots(bulbs: list[int], k: int) -> int:
    ...

Examples

Example 1:

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

Day by day:

On day 2, bulbs at positions 1 and 3 are on, and the one bulb between them is still off.

Answer:

2

Example 2:

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

There is never a day where two on bulbs have exactly one off bulb between them.

Answer:

-1

First Thought: Simulate Each Day

A direct approach is to simulate each day.

After turning on a bulb, we check whether there are two turned-on bulbs whose positions differ by k + 1, and whether every bulb between them is still off.

This works, but checking many pairs and many middle bulbs can become too slow.

We need a way to reason about the day each bulb turns on.

Key Insight

Instead of thinking day by day, build an array days.

Let:

days[position]

be the day when the bulb at position turns on.

For example:

bulbs = [1, 3, 2]

means:

So:

days = [1, 3, 2]

Now suppose two endpoint bulbs are at positions left and right.

They have exactly k bulbs between them when:

right - left - 1 = k

or:

right = left + k + 1

For these two endpoint bulbs to be valid on some day, every position between them must turn on later than both endpoints.

That means:

days[mid] > max(days[left], days[right])

for every middle position mid.

The earliest day for this pair is:

max(days[left], days[right])

because both endpoint bulbs must be on.

Sliding Window View

We can look at every window of length k + 2.

The two endpoints are candidates.

The k positions inside the window must all bloom later than both endpoints.

For a window:

left ... right

where:

right = left + k + 1

the condition is:

days[i] > days[left] and days[i] > days[right]

for every i between left and right.

If the condition holds, then this window gives a valid answer:

max(days[left], days[right])

We take the minimum over all valid windows.

Algorithm

1. Let n = len(bulbs).
2. Build days, where days[pos - 1] is the day when position pos turns on.
3. Set:

   left = 0
   right = k + 1
4. While right < n:
   • Scan positions between left and right.
   • If any middle position blooms earlier than either endpoint, this window is invalid.
   • Move left to that middle position and set right = left + k + 1.
   • If no middle position breaks the condition, update the answer with max(days[left], days[right]).
   • Then move to the next candidate window.
5. Return the best answer, or -1 if none exists.

The important optimization is how we move the window.

If a middle position i turns on earlier than one endpoint, then any window starting between left and i cannot use the old endpoint correctly. So we can jump left directly to i.

Walkthrough

Consider:

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

Build days:

So:

days = [1, 3, 2]

Since k = 1, each window has length 3.

Start:

left = 0
right = 2

Window:

positions 1, 2, 3

Endpoint days:

days[0] = 1
days[2] = 2

Middle day:

days[1] = 3

The middle bulb turns on later than both endpoints.

So on day:

max(1, 2) = 2

the two endpoint bulbs are on and the middle bulb is still off.

Answer:

2

Correctness

The array days gives the exact day each position turns on.

For two bulbs to have exactly k bulbs between them, their positions must be exactly k + 1 apart. Therefore every possible valid pair is the pair of endpoints of some window of length k + 2.

For such a window, the endpoint bulbs are both on at day max(days[left], days[right]).

The k bulbs between them are all off on that day exactly when every middle position turns on later than both endpoints.

So the condition checked by the algorithm is exactly the problem condition for that endpoint pair.

The algorithm examines all relevant endpoint pairs. When a middle position invalidates the current window, moving left to that middle position does not skip a valid answer. That middle position turns on earlier than at least one endpoint, so any window whose left endpoint lies before it and whose right endpoint lies after it would contain this early middle bulb and would be invalid.

Thus every possible valid window is either checked or safely skipped.

Whenever the algorithm finds a valid window, it computes the first day when both endpoints are on. Taking the minimum of these days gives the earliest valid day.

Therefore, the algorithm returns the correct answer.

Complexity

Let n be the number of bulbs.

Implementation

class Solution:
    def kEmptySlots(self, bulbs: list[int], k: int) -> int:
        n = len(bulbs)

        days = [0] * n
        for day, position in enumerate(bulbs, start=1):
            days[position - 1] = day

        answer = float("inf")

        left = 0
        right = 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:
                answer = min(answer, max(days[left], days[right]))
                left = right
                right = left + k + 1

        return -1 if answer == float("inf") else answer

Code Explanation

We first convert the bloom order into a day lookup:

days = [0] * n
for day, position in enumerate(bulbs, start=1):
    days[position - 1] = day

This changes the view from:

day -> position

to:

position -> day

That makes it easier to check whether the bulbs between two positions turn on later than the endpoints.

The first candidate window is:

left = 0
right = k + 1

These two endpoints have exactly k positions between them.

For every middle position:

for i in range(left + 1, right):

we check whether it turns on before either endpoint:

if days[i] < days[left] or days[i] < days[right]:

If so, this window cannot work because that middle bulb is already on before both endpoints are on.

We move the window:

left = i
right = left + k + 1

If no middle position breaks the rule, the window is valid.

Then the day when the condition first holds is:

max(days[left], days[right])

We keep the smallest such day.

Testing

def run_tests():
    s = Solution()

    assert s.kEmptySlots([1, 3, 2], 1) == 2
    assert s.kEmptySlots([1, 2, 3], 1) == -1

    assert s.kEmptySlots([1, 2], 0) == 2
    assert s.kEmptySlots([2, 1], 0) == 2

    assert s.kEmptySlots([6, 5, 8, 9, 7, 1, 10, 2, 3, 4], 2) == 8
    assert s.kEmptySlots([3, 1, 5, 4, 2], 1) == 2

    print("all tests passed")

run_tests()

Test meaning: