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:

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

Function shape:

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

Examples

Example 1:

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

Windows:

Example 2:

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:

max(nums[i:i + k])

Code:

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:

O(n * k)

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

Key Insight

Adjacent windows overlap heavily.

For example:

[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:

So the maximum of the current window is always:

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:

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:

i - k + 1

An index is outside the window if:

index <= i - k

Walkthrough

Use:

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

We store indices in the deque.

Final answer:

[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

Here, n is the length of nums.

Implementation

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:

dq = deque()

Remove indices that no longer belong to the current window:

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

For a window ending at i, valid indices are:

i - k + 1 through i

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

Then remove weaker candidates from the back:

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

This keeps the deque decreasing by value.

Add the current index:

dq.append(i)

Once the first full window exists:

if i >= k - 1:

the front of the deque is the maximum:

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

Testing

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()