# 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

| Item | Meaning |
|---|---|
| Input | `bulbs`, a permutation of positions, and integer `k` |
| Output | Earliest day satisfying the condition, or `-1` |
| Position indexing | Bulb positions are `1`-based |
| Day indexing | Days are `1`-based |
| Condition | Two on bulbs with exactly `k` off bulbs between them |

Example function shape:

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

## Examples

Example 1:

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

Day by day:

| Day | Turned-on position | State |
|---:|---:|---|
| 1 | 1 | `[1, 0, 0]` |
| 2 | 3 | `[1, 0, 1]` |
| 3 | 2 | `[1, 1, 1]` |

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

Answer:

```python
2
```

Example 2:

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

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

Answer:

```python
-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:

```python
days[position]
```

be the day when the bulb at `position` turns on.

For example:

```python
bulbs = [1, 3, 2]
```

means:

| Position | Turns on at day |
|---:|---:|
| 1 | 1 |
| 2 | 3 |
| 3 | 2 |

So:

```python
days = [1, 3, 2]
```

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

They have exactly `k` bulbs between them when:

```text
right - left - 1 = k
```

or:

```text
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:

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

for every middle position `mid`.

The earliest day for this pair is:

```text
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:

```text
left ... right
```

where:

```text
right = left + k + 1
```

the condition is:

```text
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:

```text
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:
   ```python
   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:

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

Build `days`:

| Position | Index | Day |
|---:|---:|---:|
| 1 | 0 | 1 |
| 2 | 1 | 3 |
| 3 | 2 | 2 |

So:

```python
days = [1, 3, 2]
```

Since `k = 1`, each window has length `3`.

Start:

```text
left = 0
right = 2
```

Window:

```text
positions 1, 2, 3
```

Endpoint days:

```text
days[0] = 1
days[2] = 2
```

Middle day:

```text
days[1] = 3
```

The middle bulb turns on later than both endpoints.

So on day:

```text
max(1, 2) = 2
```

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

Answer:

```python
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.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each index becomes part of the scan a constant number of times |
| Space | `O(n)` | We store the `days` array |

## Implementation

```python
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:

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

This changes the view from:

```text
day -> position
```

to:

```text
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:

```python
left = 0
right = k + 1
```

These two endpoints have exactly `k` positions between them.

For every middle position:

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

we check whether it turns on before either endpoint:

```python
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:

```python
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:

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

We keep the smallest such day.

## Testing

```python
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:

| Test | Expected | Why |
|---|---:|---|
| `[1, 3, 2]`, `k = 1` | `2` | Official positive example |
| `[1, 2, 3]`, `k = 1` | `-1` | Official negative example |
| `[1, 2]`, `k = 0` | `2` | Adjacent bulbs, no empty slot required |
| `[2, 1]`, `k = 0` | `2` | Adjacent bulbs in reverse order |
| Larger case | `8` | Checks window jumps |
| `[3, 1, 5, 4, 2]`, `k = 1` | `2` | Valid pair appears early |