A sliding window can maintain a sum in $O(1)$ per step, because adding and removing are both reversible arithmetic. A maximum is not: when the current maximum slides out of the window, you have no idea what the new maximum is, and rescanning the window costs $O(k)$ — back to $O(n \cdot k)$ overall.

The fix is a monotonic deque: a double-ended queue holding indices whose values are kept sorted. The window’s maximum is then always at the front, readable in $O(1)$, and the whole scan stays $O(n)$ because each index is pushed once and popped once.

What you’ll learn

• Why a heap is the wrong tool here, and what a deque gives you instead.
• The “pop from the back while smaller, pop from the front when expired” template.
• The amortised argument that makes an inner whilewhile loop still $O(n)$.
• Three real LeetCode problems solved in the browser: 239, 1696, 1438.

The cue

The template

from collections import deque
 
 
def sliding_window_maximum(nums, k):
    dq = deque()          # holds INDICES; their values are strictly decreasing
    out = []
 
    for i, x in enumerate(nums):
        # 1. maintain monotonicity: anything smaller than x is now useless
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
 
        # 2. evict the front if it has slid out of the window
        if dq[0] <= i - k:
            dq.popleft()
 
        # 3. the front is the window's maximum
        if i >= k - 1:
            out.append(nums[dq[0]])
 
    return out
 
 
print(sliding_window_maximum([1, 3, -1, -3, 5, 3, 6, 7], 3))   # [3, 3, 5, 5, 6, 7]

from collections import deque
 
 
def sliding_window_maximum(nums, k):
    dq = deque()          # holds INDICES; their values are strictly decreasing
    out = []
 
    for i, x in enumerate(nums):
        # 1. maintain monotonicity: anything smaller than x is now useless
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
 
        # 2. evict the front if it has slid out of the window
        if dq[0] <= i - k:
            dq.popleft()
 
        # 3. the front is the window's maximum
        if i >= k - 1:
            out.append(nums[dq[0]])
 
    return out
 
 
print(sliding_window_maximum([1, 3, -1, -3, 5, 3, 6, 7], 3))   # [3, 3, 5, 5, 6, 7]

Three moves, always in this order: pop the back to restore monotonicity, pop the front to drop expired indices, read the front for the answer.

Why it is O(n) despite the inner while

Each index is appendappended exactly once and poppopped at most once, so the total number of deque operations across the entire run is at most $2n$. The inner whilewhile can run many times on one iteration, but only by consuming pushes that already happened — it can never run more times in total than there were pushes.

The variant map

Practice — real LeetCode problems

LC 239 — Sliding Window Maximum · Hard

Problem. Given an array numsnums and a window size kk, return an array of the maximum value in each window as it slides from left to right.

Constraints. 1 <= len(nums) <= 10^51 <= len(nums) <= 10^5, 1 <= k <= len(nums)1 <= k <= len(nums), -10^4 <= nums[i] <= 10^4-10^4 <= nums[i] <= 10^4.

Examples. nums = [1,3,-1,-3,5,3,6,7], k = 3nums = [1,3,-1,-3,5,3,6,7], k = 3 gives [3,3,5,5,6,7][3,3,5,5,6,7] · nums = [1], k = 1nums = [1], k = 1 gives [1][1]

LC 1696 — Jump Game VI · Medium

Problem. You start at index 00 and must reach the last index. From index ii you may jump to any index in [i+1, i+k][i+1, i+k]. Your score is the sum of nums[j]nums[j] over every index you land on (including 00 and the last). Return the maximum score.

Constraints. 1 <= len(nums), k <= 10^51 <= len(nums), k <= 10^5, -10^4 <= nums[i] <= 10^4-10^4 <= nums[i] <= 10^4.

Examples. nums = [1,-1,-2,4,-7,3], k = 2nums = [1,-1,-2,4,-7,3], k = 2 gives 77 · nums = [10,-5,-2,4,0,3], k = 3nums = [10,-5,-2,4,0,3], k = 3 gives 1717 · nums = [1,-5,-20,4,-1,3,-6,-3], k = 2nums = [1,-5,-20,4,-1,3,-6,-3], k = 2 gives 00

LC 1438 — Longest Continuous Subarray With Absolute Diff ≤ Limit · Medium

Problem. Return the length of the longest contiguous subarray in which the difference between the maximum and minimum element is at most limitlimit.

Constraints. 1 <= len(nums) <= 10^51 <= len(nums) <= 10^5, 1 <= nums[i] <= 10^91 <= nums[i] <= 10^9, 0 <= limit <= 10^90 <= limit <= 10^9.

Examples. nums = [8,2,4,7], limit = 4nums = [8,2,4,7], limit = 4 gives 22 · nums = [10,1,2,4,7,2], limit = 5nums = [10,1,2,4,7,2], limit = 5 gives 44 · nums = [4,2,2,2,4,4,2,2], limit = 0nums = [4,2,2,2,4,4,2,2], limit = 0 gives 33

LeetCode problem set

Interview follow-ups

Edge-case checklist

• k = 1k = 1 — every window is one element; output equals the input.
• k = len(nums)k = len(nums) — one window; the answer is a single global max.
• All equal values — exercises the <=<= vs << choice; both work but only <=<= keeps the deque small.
• Strictly increasing input — the deque never exceeds length 1.
• Strictly decreasing input — the deque grows to kk; this is the space worst case.
• Negative values only — do not initialise a running best to 00.
• limit = 0limit = 0 (1438) — valid; only runs of identical values qualify.
• Front eviction guard (1438) — pop the front only when its index equals leftleft.

Recap

• A sliding window handles sums by arithmetic, but an extremum needs a monotonic deque: indices in, values sorted, extremum at the front.
• Three moves in order: pop the back while dominated, pop the front when expired, read the front.
• Store indices, never values — expiry is positional.
• $O(n)$ amortised: each index is pushed once and popped once, so the inner whilewhile cannot exceed the total number of pushes.
• The pattern generalises past arrays: over dpdp it removes the kk from windowed-DP transitions (1696), and over prefix sums it rescues sum-windows from negative numbers (862).

Next: Prefix Sums and Difference Arrays — the other answer to “negative numbers broke my window”, and the $O(1)$ range-query workhorse.