# LeetCode 239: Sliding Window Maximum

## Problem Restatement

We are given an integer array `nums` and an integer `k`.

There is a sliding window of size `k`. It starts at the left side of the array and moves one position to the right each time.

For each window, we need to return the maximum value inside that window.

LeetCode gives this example:

```text
Input:  nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
```

The constraints allow up to `10^5` elements, so checking every window directly can be too slow. The standard efficient solution uses a monotonic deque.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums`, integer window size `k` |
| Output | Array of window maximums |
| Window size | Exactly `k` |
| Number of windows | `len(nums) - k + 1` |
| Target | Linear time |

Function shape:

```python
class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        ...
```

## Examples

Example 1:

```text
Input:  nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
```

Windows:

| Window | Maximum |
|---|---:|
| `[1,3,-1]` | `3` |
| `[3,-1,-3]` | `3` |
| `[-1,-3,5]` | `5` |
| `[-3,5,3]` | `5` |
| `[5,3,6]` | `6` |
| `[3,6,7]` | `7` |

Example 2:

```text
Input:  nums = [1], k = 1
Output: [1]
```

There is only one window, and its maximum is `1`.

## First Thought: Brute Force

The direct solution is to inspect every window.

For each start index `i`, compute:

```python
max(nums[i:i + k])
```

Code:

```python
class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        ans = []

        for i in range(len(nums) - k + 1):
            ans.append(max(nums[i:i + k]))

        return ans
```

This is simple, but each window costs `O(k)` time.

With `n` elements, the total time is:

```text
O(n * k)
```

For large `n` and large `k`, this is too slow.

## Key Insight

Adjacent windows overlap heavily.

For example:

```text
[1, 3, -1]
   [3, -1, -3]
```

Most elements are reused.

We need a data structure that can tell us the maximum of the current window quickly while we slide.

A deque works well if we keep it in decreasing order by value.

The deque stores indices, not values.

It stores indices because we must know when an element leaves the current window.

## Monotonic Deque

The deque will satisfy two rules:

| Rule | Meaning |
|---|---|
| Indices are in increasing order | Front is the oldest candidate |
| Values are in decreasing order | Front is the largest candidate |

So the maximum of the current window is always:

```python
nums[dq[0]]
```

where `dq[0]` is the index at the front of the deque.

## Why Remove Smaller Values?

Suppose the deque has an index `j`, and we are reading index `i`.

If:

```text
nums[j] <= nums[i]
```

and `j < i`, then `nums[j]` can never be the maximum of a future window that also contains `i`.

Why?

`nums[i]` is at least as large as `nums[j]`, and `i` is newer, so it stays in the sliding window longer.

Therefore, `j` is useless and can be removed from the back of the deque.

This is the reason we maintain decreasing values.

## Algorithm

Create an empty deque `dq`.

For each index `i`:

1. Remove indices from the front if they are outside the current window.
2. Remove indices from the back while their values are less than or equal to `nums[i]`.
3. Add index `i` to the back.
4. If the first full window has formed, append `nums[dq[0]]` to the answer.

The current window ending at `i` starts at:

```text
i - k + 1
```

An index is outside the window if:

```text
index <= i - k
```

## Walkthrough

Use:

```text
nums = [1,3,-1,-3,5,3,6,7]
k = 3
```

We store indices in the deque.

| `i` | `nums[i]` | Deque Values After Insert | Output |
|---:|---:|---|---|
| `0` | `1` | `[1]` | none |
| `1` | `3` | `[3]` | none |
| `2` | `-1` | `[3, -1]` | `3` |
| `3` | `-3` | `[3, -1, -3]` | `3` |
| `4` | `5` | `[5]` | `5` |
| `5` | `3` | `[5, 3]` | `5` |
| `6` | `6` | `[6]` | `6` |
| `7` | `7` | `[7]` | `7` |

Final answer:

```text
[3, 3, 5, 5, 6, 7]
```

## Correctness

The deque only contains indices from the current window because the algorithm removes indices from the front once they become too old.

The deque values are always decreasing from front to back. Before adding a new index `i`, the algorithm removes all smaller or equal values from the back. Then `i` is appended. This preserves decreasing order.

Because the deque is decreasing by value, the largest value among all stored candidates is always at the front.

Any removed back index cannot become a future maximum, because the new value is at least as large and appears later in the array. It will remain available for at least as long as the removed index.

Therefore, after each full window is formed, `nums[dq[0]]` is exactly the maximum value in that window.

Since the algorithm appends one maximum for every full window, it returns the correct result.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each index is added once and removed at most once |
| Space | `O(k)` | The deque stores indices from the current window |

Here, `n` is the length of `nums`.

## Implementation

```python
from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        dq = deque()
        ans = []

        for i, num in enumerate(nums):
            while dq and dq[0] <= i - k:
                dq.popleft()

            while dq and nums[dq[-1]] <= num:
                dq.pop()

            dq.append(i)

            if i >= k - 1:
                ans.append(nums[dq[0]])

        return ans
```

## Code Explanation

The deque stores indices:

```python
dq = deque()
```

Remove indices that no longer belong to the current window:

```python
while dq and dq[0] <= i - k:
    dq.popleft()
```

For a window ending at `i`, valid indices are:

```text
i - k + 1 through i
```

So any index `<= i - k` is too old.

Then remove weaker candidates from the back:

```python
while dq and nums[dq[-1]] <= num:
    dq.pop()
```

This keeps the deque decreasing by value.

Add the current index:

```python
dq.append(i)
```

Once the first full window exists:

```python
if i >= k - 1:
```

the front of the deque is the maximum:

```python
ans.append(nums[dq[0]])
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3) == [3,3,5,5,6,7]
    assert s.maxSlidingWindow([1], 1) == [1]
    assert s.maxSlidingWindow([9, 8, 7, 6], 2) == [9, 8, 7]
    assert s.maxSlidingWindow([1, 2, 3, 4], 2) == [2, 3, 4]
    assert s.maxSlidingWindow([4, 4, 4], 2) == [4, 4]
    assert s.maxSlidingWindow([-7, -8, 7, 5, 7, 1, 6, 0], 4) == [7, 7, 7, 7, 7]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[1,3,-1,-3,5,3,6,7]`, `k = 3` | Standard example |
| `[1]`, `k = 1` | Minimum input |
| Decreasing array | Old maximum expires |
| Increasing array | New value removes old values |
| Duplicate values | Equal values handled correctly |
| Negative and positive values | General integer behavior |