Sliding Window Maximum and the Monotonic Deque

You stop the nested loops of O(n * k) by storing indices in a double-ended queue that stays strictly decreasing from front to back. When a new element arrives, pop smaller elements from the tail, remove indices outside the current window from the head, and read the maximum instantly at the front.

Why Nested Loops Fail

A brute force scan checks every window of size k separately. If n is 100,000 and k is 40,000, that scan performs 4 billion operations and times out on the judge. The problem is redundant work. When the window slides right by one step, k-1 elements stay identical. Recomputing their maximum from scratch ignores what you already calculated.

The Monotonic Deque Mechanism

A monotonic deque stores indices, not values, in decreasing order of their corresponding array elements. Look at the array [1, 3, -1, -3] with k = 3. At index 1, the value 3 arrives. It is larger than the previous element 1, so 0 pops off the tail of the deque. The deque holds indices, so 1 sits at the front. When index 3 arrives with value -3, it enters the tail because it is smaller than 3 and -1, keeping the structure intact.

Each index enters the deque once and leaves the deque once. The total push and pop operations across the entire array equal 2n, which guarantees O(n) time complexity even if k is large. If you used a balanced binary search tree or a max-heap, insertions would cost O(log k), raising the total time to O(n log k) and failing strict time limits.

A Hand Calculation

Take the array [1, 3, -1, -3, 5, 3] with k = 3.

1. Index 0 (val = 1): Deque is [0]. Window [1] max is none yet.
2. Index 1 (val = 3): 3 > 1, pop 0. Deque is [1]. Window [1, 3] max is none.
3. Index 2 (val = -1): -1 < 3. Deque is [1, 2]. Window [1, 3, -1] max is at front index 1, which gives 3.
4. Index 3 (val = -3): Index 1 is out of the window bounds [3 - 3 + 1, 3], so pop head. Deque is [2, 3]. Window [3, -1, -3] max is at index 2, which gives -1.
5. Index 4 (val = 5): 5 beats -3 and -1, pop both. Deque is [4]. Window [-1, -3, 5] max is at index 4, which gives 5.

The Rule of Thumb for Deques

Keep these four rules in mind for every sliding window problem that needs extremes:

• Store indices in the deque, not the actual values, so you can check if an element is outside the current window by comparing index bounds.
• Maintain strict monotonic order by popping the tail while the incoming element is greater for maximums, or smaller for minimums.
• Evict from the head whenever the front index is less than i - k + 1.
• Read the answer for the current window directly from the front of the deque before moving the right pointer forward.

Beyond Basic Windows

The same deque logic applies when the window size is not fixed. Consider Shortest Subarray with Sum at Least K, where the window expands and shrinks based on prefix sums. Here, the monotonic queue stores prefix sum indices and pops elements from the head whenever the sum condition is met, turning what looks like an O(n^2) subarray search into a clean O(n) pass.

Practice this exact implementation on DSA Tracker today by writing the maxSlidingWindow function without looking at a reference solution.

Keep going with the step-by-step visualizer and practice problems.

Further reading: Binary search on Wikipedia.