Sliding Window Maximum — The Parade Watch

Boss 6: The Parade Watch

Final boss of the dungeon.

Every window so far cared about what's inside: counts, quotas, duplicates. This one asks about who's in charge: the maximum of each window. Sounds simpler. Isn't. The maximum is a diva, when it leaves the window you need to know who's next in line, and the window's counts can't tell you that.

The answer is a new tool riding inside the window. This boss is really a two-for-one: you clear the dungeon and pick up the monotonic deque, which returns in the Stack dungeon's harder cousins and all over LeetCode Hard.

The story

Independence day parade, live broadcast, you're on camera duty. Floats roll past in a fixed line. Your frame shows exactly k = 3 floats at once, and it slides forward one float at a time.

Float heights, in parade order:

heights = [1, 3, -1, -3, 5, 3, 6, 7]

(Yes, one float is height -3. It's a submarine on wheels. Parades are weird.)

After every slide, the director wants the tallest float currently in frame, instantly, for the on-screen graphic:

frame [1  3  -1]           → tallest 3
frame    [3  -1  -3]       → tallest 3
frame       [-1  -3  5]    → tallest 5
frame          [-3  5  3]  → tallest 5
frame             [5  3  6] → tallest 6
frame                [3  6  7] → tallest 7

Expected output: [3, 3, 5, 5, 6, 7].

The problem, dressed up properly

You are given an array of integers nums and an integer k. There is a sliding window of size k moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position, return the max of the window.

Return an array of each window's max.

LeetCode 239, marked Hard.

The naive attempt

Scan all k floats per frame.

def max_sliding_window(nums, k):
    return [max(nums[i:i+k]) for i in range(len(nums) - k + 1)]

One line, and O(n·k). With 100,000 floats and k = 50,000, that's billions of comparisons. The broadcast lags, the director throws a headset.

The frustrating part: consecutive frames share k-1 floats. All that shared knowledge, recomputed from zero every step. But you can't just "keep the max and update it", because when the current max exits the frame, you have no idea who the runner-up was. That's the real puzzle: maintaining not just the champion, but the whole line of succession.

The weapon: the line of succession

Here's the observation that cracks it. A new float enters the frame. Look at any shorter float that entered before it:

• It's shorter, so it can't be the max while the new float is in frame.
• It entered earlier, so it leaves the frame before the new float does.

Shorter and gone sooner. There is no future frame in which that float matters. Not "probably won't matter", provably never. Delete it from consideration, permanently.

So keep a deque (double-ended queue) of floats that could still matter, storing their indices. Maintain it with three moves per step:

1. New float enters: pop everyone off the back of the deque who is shorter than it (they're obsolete, by the argument above), then push the new float's index on the back.
2. Front too old? If the index at the front has slid out of the frame, pop it from the front.
3. Answer the director: the front of the deque is the current frame's max. Always.

Because every entering float purges the shorter ones behind it, the heights in the deque are always strictly decreasing from front to back. That's why it's called a monotonic deque. The front is the champion, and behind it stands the succession line: each member is the tallest float that entered after everyone in front of it. When the champion retires out of frame, the next in line is already standing there. No recount, no election.

Watching it work

heights = [1, 3, -1, -3, 5, 3, 6, 7], k = 3. Deque shown as heights, front on the left.

R   float   pop back?          deque after   front old?   output
0   1       -                  [1]           -            (frame not full)
1   3       pop 1 (shorter)    [3]           -            (frame not full)
2   -1      no                 [3, -1]       no           3
3   -3      no                 [3, -1, -3]   no           3
4   5       pop -3, -1, 3!     [5]           no           5
5   3       no                 [5, 3]        no           5
6   6       pop 3, pop 5       [6]           no           6
7   7       pop 6              [7]           no           7

Step 4 is the boss fight in miniature: the submarine era ends, float 5 walks in and dismisses the entire deque, including the reigning champion 3, which was about to age out anyway. And note step 3: -3 gets to join the line even though it's pathetic, because everyone ahead of it is taller, it's legitimately third in succession. If floats 3 and -1 had left the frame with -3 still inside, -3 would have been the max. Every member of the deque has a possible future in which it reigns. That's the membership test.

Output: [3, 3, 5, 5, 6, 7]. Matches.

The code

from collections import deque
 
def max_sliding_window(nums: list[int], k: int) -> list[int]:
    dq = deque()          # indices; heights strictly decreasing front→back
    out = []
    for r in range(len(nums)):
        # 1. new float dismisses shorter floats at the back
        while dq and nums[dq[-1]] < nums[r]:
            dq.pop()
        dq.append(r)
 
        # 2. front retired out of frame?
        if dq[0] <= r - k:
            dq.popleft()
 
        # 3. frame full → front is the answer
        if r >= k - 1:
            out.append(nums[dq[0]])
    return out

Gotchas

1. Storing values instead of indices. See the callout. Without indices, expiring the front is guesswork, and duplicates break everything.

2. Popping the back with <= versus <. With < (strict), equal-height floats coexist in the deque, which is correct but keeps a few extra members. With <=, an equal newcomer dismisses the older equal, also correct, since the newcomer leaves the frame later it fully replaces the older one. Both pass. Popping the front eagerly, though, is wrong: only expire the front when it's actually out of frame.

3. Expiring the front with the wrong boundary. The frame at step r covers indices r - k + 1 through r. The front expires when dq[0] <= r - k, not < r - k, not <= r - k + 1. Off-by-one here returns wrong answers only on inputs where the max sits at the frame's trailing edge, which is exactly the kind of bug that survives casual testing.

4. Reaching for a heap. A max-heap gives you the max, sure, but lazy-deleting expired floats costs O(log n) per step and a whole lot of bookkeeping, O(n log n) total. The deque is O(n) flat and simpler once you know the succession argument. Heaps hold grudges, deques let go.

Complexity

Every index enters the deque exactly once and leaves at most once, from one end or the other. All the whiles in the world can't exceed that budget, the same amortized argument as Boss 2.

Time: O(n). Space: O(k) for the deque.

Boss down. Dungeon down. XP gained.

The graphic updates instantly, the director calls it the smoothest broadcast in years, and the submarine float wins "most creative" for some reason.

What you're carrying out of Dungeon 5:

• The grow-shrink rhythm: extend right while valid, pull left until valid again (Tasting Counter)
• Budgeted validity: a window may be broken by at most k, checked as length - maxf ≤ k (Marquee)
• Fixed windows with enter-and-leave fingerprint updates, no shrink logic at all (Spice Blend)
• The minimum-window inversion: squeeze while valid, record every squeeze (Market Run)
• The monotonic deque: a line of succession that answers "max of window" in O(1) (Parade)
• And under all of it, one amortized argument: edges that only move forward means O(n), always

One dungeon, one shape: a contiguous stretch and two edges with rules. You'll recognize it now in problems that never say the word "window".

Next dungeon: Linked List. The arrays end here. In Dungeon 6, data stops sitting in neat rows and starts hiding behind pointers, each node knowing only where the next one lives. Reversal, cycle detection with two runners on a track, merging chains, and the pointer surgery that either clicks forever or crashes on a null. Bring gloves.

See you in Dungeon 6.