Sliding Window Maximum: why a monotonic deque collapses O(n*k) to O(n)

The window slides. The maximum changes. And every naive attempt to track it costs O(k) per step — tolerable when k is tiny, painful when k is close to n, catastrophic when both are at 10^5. The question this problem is really asking is: can you maintain a running maximum across a moving window without recomputing it from scratch each time?

The answer is yes, and the mechanism is a monotonic deque. Before getting there, it is worth spending a moment with the brute force — not to dismiss it, but to see exactly what work it is doing unnecessarily.

The problem

You are given an array of integers and a sliding window of size k that moves from left to right one position at a time; at each position you can only see the k numbers inside the window. Return the array of maximums — one per window position. Full statement: LeetCode 239.

Constraints:
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- 1 <= k <= nums.length

What the constraints force

n is up to 10^5 and k is anywhere from 1 to n. There are n - k + 1 windows. If you scan each window fully, you spend O(k) per window and O(n * k) total. When k = n / 2, that is O(n^2 / 2). At n = 10^5, that is five billion operations. Nothing about the time limit survives that.

The constraint 1 <= k <= n means you never have an empty window and never need to handle a window that does not fit. The value range [-10^4, 10^4] means negatives are normal — no tricks using 0 as a sentinel. The maximum value in any window is always a legitimate integer.

What the constraints force together is a single conclusion: you need O(n) time. The window size k cannot appear in your dominant term. Everything else falls out of that.

Approach 1: Brute Force

For each window starting position, scan all k elements and record the maximum. Direct, obvious, and too slow for large input.

class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        result = []
        for i in range(n - k + 1):
            window_max = nums[i]
            for j in range(i, i + k):
                window_max = max(window_max, nums[j])
            result.append(window_max)
        return result

public class Solution {
    public int[] MaxSlidingWindow(int[] nums, int k) {
        int n = nums.Length;
        int[] result = new int[n - k + 1];
        for (int i = 0; i <= n - k; i++) {
            int windowMax = nums[i];
            for (int j = i; j < i + k; j++) {
                windowMax = Math.Max(windowMax, nums[j]);
            }
            result[i] = windowMax;
        }
        return result;
    }
}

Time: O(n * k) — outer loop runs n - k + 1 times, inner loop runs k times each. Space: O(1) auxiliary — result array excluded by convention.

The brute force has a specific inefficiency: when the window slides one position right, you recompute the max over k - 1 elements that were already in the previous window. You are throwing away information. The deque approach keeps exactly the information you need.

Approach 2: Monotonic Deque

The idea is to maintain a deque of indices whose corresponding values are in decreasing order. The front of the deque always holds the index of the maximum of the current window. When the window slides, you:

1. Evict the front if it has slid out of the window.
2. Before pushing the new index, pop from the back any indices whose values are <= the new element — those elements are now useless, because the new element is both larger and will remain in the window longer.
3. Push the new index to the back.
4. Read the maximum from the front.

Why <= rather than < when popping? Because if two equal elements exist and the earlier one is about to leave the window, keeping it creates a ghost maximum. Popping on <= keeps the deque clean and the front always valid.

from collections import deque
 
class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        dq: deque[int] = deque()  # stores indices, not values
        result = []
 
        for i in range(len(nums)):
            # 1. evict front if it is outside the current window
            while dq and dq[0] < i - k + 1:
                dq.popleft()
 
            # 2. pop from back any index whose value is <= nums[i]
            while dq and nums[dq[-1]] <= nums[i]:
                dq.pop()
 
            # 3. push current index
            dq.append(i)
 
            # 4. the window is full once i >= k - 1
            if i >= k - 1:
                result.append(nums[dq[0]])
 
        return result

using System;
using System.Collections.Generic;
 
public class Solution {
    public int[] MaxSlidingWindow(int[] nums, int k) {
        var dq = new LinkedList<int>();  // stores indices
        var result = new List<int>();
 
        for (int i = 0; i < nums.Length; i++) {
            // 1. evict front if outside window
            while (dq.Count > 0 && dq.First.Value < i - k + 1) {
                dq.RemoveFirst();
            }
 
            // 2. pop back while back value <= nums[i]
            while (dq.Count > 0 && nums[dq.Last.Value] <= nums[i]) {
                dq.RemoveLast();
            }
 
            // 3. push current index
            dq.AddLast(i);
 
            // 4. record result once first window is complete
            if (i >= k - 1) {
                result.Add(nums[dq.First.Value]);
            }
        }
 
        return result.ToArray();
    }
}

Time: O(n) — every index enters the deque exactly once and leaves at most once. The inner while loops are amortized O(1) per outer iteration. Space: O(k) — the deque holds at most k indices at any time.

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

Step by step:

• i=0: deque empty, push 0. dq=[0]. Not yet k-1=2.
• i=1: nums[1]=3 > nums[0]=1, pop 0. Push 1. dq=[1]. Still not ready.
• i=2: nums[2]=-1 < nums[1]=3, back stays. Push 2. dq=[1,2]. i >= 2 -> result gets nums[1]=3.
• i=3: front=1, 1 >= 3-3+1=1, still in window. nums[3]=-3 < nums[2]=-1, back stays. Push 3. dq=[1,2,3]. Result gets nums[1]=3.
• i=4: front=1, 1 < 4-3+1=2, evict. dq=[2,3]. Now nums[4]=5 > nums[3]=-3, pop 3. nums[4]=5 > nums[2]=-1, pop 2. Push 4. dq=[4]. Result gets nums[4]=5.
• i=5: front=4, in window. nums[5]=3 < nums[4]=5, back stays. Push 5. dq=[4,5]. Result gets nums[4]=5.
• i=6: front=4, 4 < 6-3+1=4 is false (4 is not < 4), front stays. nums[6]=6 > nums[5]=3, pop 5. nums[6]=6 > nums[4]=5, pop 4. Push 6. dq=[6]. Result gets nums[6]=6.
• i=7: front=6, 6 < 7-3+1=5 is false. nums[7]=7 > nums[6]=6, pop 6. Push 7. dq=[7]. Result gets nums[7]=7.

Final result: [3, 3, 5, 5, 6, 7]. Matches the expected output.

The invariant throughout: the deque is always monotonically decreasing in value from front to back, and every index in the deque is within the current window.

Edge cases that deserve a closer look

k = 1: Every element is its own window. The deque always contains exactly one element at a time. At each step, the back-pop loop empties the deque immediately because the single old element is <= the current one, or the eviction step clears it. Result is just a copy of nums. Both approaches handle this correctly without special-casing.

k = n: Exactly one window, containing all elements. The deque collects indices through the entire array during the warmup phase and yields one result at i = n - 1. The brute force trivially returns [max(nums)].

All elements equal (e.g., [5, 5, 5, 5]): The back-pop uses <=, so equal elements are popped. The deque always contains exactly one index — the most recent one. The front-eviction then removes it on schedule. The result is a constant array of the repeated value. If you used < instead of <= in the pop condition, the deque could grow to hold stale equal values; after one exits the window you would evict the front but the second entry — still pointing to a valid value — would correctly yield the right answer. Using <= is cleaner and still correct because all equal elements have the same value.

Strictly decreasing array (e.g., [9, 7, 5, 3], k = 2): The deque never pops from the back — every new element is smaller. The deque grows to size 2, then front-evictions keep it at size 1 as the window slides. You always read the leftmost element in the window as the maximum.

Strictly increasing array (e.g., [1, 3, 5, 7], k = 2): Every new element is larger than all prior ones. The back-pop empties the deque completely at each step. The deque always has exactly one index — the current position — and the result is nums[1:] (dropping the first element), which is correct.

Single element n = 1, k = 1: One window, one element. The loop runs once, the deque gets [0], i >= k-1=0 is true, result is [nums[0]].

The deque is a "useful candidate" filter

The mental model I reach for: the deque stores the indices of the candidates that could still be the window maximum in the future. An index is a candidate only if:

1. It is within the current window (front eviction handles this).
2. There is no newer index in the window with a larger value (back-pop handles this).

Any index that fails condition 2 can be dropped forever — if element j is in the window with nums[j] <= nums[i] and j < i, then while element j is still in the window, element i is also in the window and is at least as large. And after element j leaves, element i is still potentially there. So j contributes nothing.

This is why the deque ends up sorted decreasingly: every time you push a new index, you have already removed everything smaller. The front is always the largest remaining candidate.

Comparison table

There is no threshold where I would ship the brute force. Even at small k, the deque code is only marginally more complex and scales to any input. I would write the deque solution directly in an interview after the constraints are known — the n = 10^5 bound closes the discussion.

Where this sits in the sliding window series

The earlier problems in this series — Best Time to Buy and Sell Stock, Longest Repeating Character Replacement, Minimum Window Substring — all use a two-pointer or shrinkable window. This problem introduces a different primitive: the monotonic deque. Instead of adjusting window boundaries based on a validity condition, you maintain an auxiliary structure that tracks the maximum across a fixed-size window.

The underlying pattern is transferable: any time you need a running extremum (max or min) over a fixed-size sliding window, a monotonic deque gives you O(n). A min-deque just flips the pop condition from <= to >=.

Four sibling problems that develop the same idea:

Sliding Window Median (480) — instead of max, track the median. A single deque is not enough; you need two heaps (a max-heap for the lower half, a min-heap for the upper half) and a rebalance step as the window slides. Much harder to implement, same sliding-window frame.

Shortest Subarray with Sum at Least K (862) — combines a monotonic deque with prefix sums. The deque tracks a monotonically increasing prefix sum, and you look for the closest earlier position that makes the subarray sum large enough. The window is not fixed-size here, which is what makes it hard.

Jump Game VI (1696) — a DP problem where the transition is dp[i] = nums[i] + max(dp[i-k..i-1]). The deque maintains the maximum of the previous k dp values, turning an O(n * k) DP into O(n). The deque structure is identical to what you built here.

Constrained Subsequence Sum (1425) — same idea as Jump Game VI: a DP where each state depends on the maximum of the previous k states. The deque optimization applies directly.

Once you have the monotonic deque pattern in your head, these four become recognizable variations rather than new problems.