239. Sliding Window Maximum

Problem¶

Given nums and a window size k, return the maximum value in every contiguous subarray of length k.

nums = [1, 3, -1, -3, 5], k = 3
windows = [[1, 3, -1], [3, -1, -3], [-1, -3, 5]]
output = [3, 3, 5]

Key trick¶

Maintain a deque of indices whose values are monotonically decreasing. Its front is always the current window's maximum, and every index is added and removed at most once.

Trap¶

A set loses duplicate counts, so removing one occurrence can remove a value still present in the window.
A Counter retains keys with zero counts unless they are explicitly deleted.
Recomputing the maximum after a removal can cost \(O(k)\) per window, producing \(O(nk)\) time.
The deque must store indices, not only values, so expired elements can be detected.

Why is it interesting?¶

It turns repeated maximum queries from \(O(nk)\) into \(O(n)\) by maintaining only elements that can still become a future maximum.

Python solution¶

from collections import deque


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

        for i, x in enumerate(nums):
            # Remove indices that are no longer inside the window.
            if q and q[0] <= i - k:
                q.popleft()

            # Smaller values cannot become maxima while x remains present.
            while q and nums[q[-1]] <= x:
                q.pop()

            q.append(i)

            # The deque's front is the maximum of the completed window.
            if i >= k - 1:
                res.append(nums[q[0]])

        return res

Time complexity: \(O(n)\).

Space complexity: \(O(k)\).

Comment on my solution¶

The set solution is incorrect because sets discard duplicates. For example, removing one 3 removes the value entirely even if another 3 remains in the window, and remove can then raise KeyError.

The Counter preserves multiplicity, but zero-count keys remain present. For [1, -1] with k = 1, the outgoing key 1 still participates in max(window.keys()).

Deleting zero-count keys would fix correctness, but recomputing max(window) can still take \(O(k)\) per window, giving \(O(nk)\) worst-case time. A max heap with lazy removal would achieve \(O(n \log n)\), while the monotonic deque achieves the optimal \(O(n)\).

# Ideas:
# - brute force is trivial and O(n x k)
# - remind me of 2D DP solution for plalindrome substrings
#   - row (start) and column (end)
#   - I think this the best way
# - As we're considering a changing max, max heap could be helpful
#   - problem with max heap is that when moving we have no way
#     to remove in O(1)/O(log k) the left element of previous
#     window if it was not the max
# - is something like prefix / suffix
# - maybe dp array of size k
# - maybe a current set of value in the sliding window with its current max
#   - shift the sliding Window
#     - remove at most one value
#     - add at most one value
#     - compute a max between 2 values only


## Solution

# WRONG
# Runtime Error: 11 / 53 testcases passed
# [1,3,1,2,0,5], 3
class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        window = set(nums[:k])
        window_max = max(window)
        res = [window_max]

        for i in range(k, len(nums)):
            prev = nums[i - k]
            new = nums[i]
            window.remove(prev)
            window.add(new)
            if prev != window_max:
                window_max = max(window_max, new)
            else:
                window_max = max(window)
            res.append(window_max)
        return res

Solution().maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3)
Solution().maxSlidingWindow([1,3,1,2,0,5], 3)


from collections import Counter
# WRONG
# Wrong Answer: 21/53 testcases passed
# [1,-1], 1
# output: [1,1]
# expected: [1,-1]
class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        window = Counter(nums[:k])
        window_max = max(window)
        res = [window_max]

        for i in range(k, len(nums)):
            prev = nums[i - k]
            new = nums[i]
            window[prev] -= 1
            window[new] += 1
            if prev != window_max:
                window_max = max(window_max, new)
            else:
                window_max = max(window.keys())
            res.append(window_max)
        return res

Extra¶

Deque - double-ended queue¶

Why are you calling it a deque in "Maintain a deque of indices" in the comments? Why not calling it a queue? Is it because of the python library name deque? Am I missing something?

A deque means double-ended queue. The algorithm must efficiently remove elements from both ends:

Remove expired indices from the front.
Remove smaller, dominated values from the back.
Add each new index to the back.

A regular FIFO queue only supports adding at the back and removing from the front. It cannot efficiently remove from the back, which this algorithm requires.

Python's collections.deque provides all needed operations in \(O(1)\):

q.popleft()  # Remove an expired index from the front.
q.pop()      # Remove a dominated index from the back.
q.append(i)  # Add the new index at the back.

So deque is not merely the Python library name; it is the precise data structure required by the algorithm.

The technique is also commonly called a monotonic queue, describing its purpose and invariant. More precisely, it is a monotonic queue implemented with a deque:

front: largest value and current maximum
back:  smallest remaining candidate

Using a Python list would make removal from the front \(O(n)\), while deque.popleft() is \(O(1)\).