You know how to track a running sum across a sliding window --- subtract the leaving element, add the entering one. O(1) per slide.

But what about the maximum? When the current max leaves the window, you cannot compute the new max from the old one. There is no “inverse of max.” You would have to re-scan every element in the window.

Think about why this is fundamentally different from sum. With a sum, every element contributes additively --- removing one element changes the total by a known, predictable amount. But max is not additive. If the window contains [3, 1, -1] and the max 3 leaves, the new max is 1. You cannot derive 1 from 3 and the entering element alone. You need to know what else is in the window.

A brute-force scan of the window costs O(k) per slide, giving O(n * k) total. For a million-element array with windows of size 1000, that is a billion operations. There has to be a smarter structure.

How expensive is that re-scanning? And is there a way to avoid it?

The array is [1, 3, -1, -3, 5, 3, 6, 7] with window size 3 --- the classic LC 239 setup. You need the maximum of every window: max([1,3,-1]), max([3,-1,-3]), max([-1,-3,5]), and so on.

On the previous screen you saw why re-scanning costs O(k) per slide. But think about what information is actually worth keeping. When the window contains [1, 3, -1], the 1 can never be the maximum --- not now, and not in any future window that still contains the 3. The 3 entered later and is bigger, so it will outlast the 1 in every window they share. The 1 is permanently dominated.

The -1, on the other hand, might matter. If 3 eventually leaves the window and no larger element has arrived, -1 could become the max by default. It is smaller, but it entered later --- so it has a longer shelf life.

This is what you are about to discover: you don't need to track every element in the window. You only need the ones that have a chance of being the maximum at some point in the future. Those elements form a specific pattern --- each one smaller than the last, sorted by when they might take the throne. What kind of data structure maintains that pattern as elements arrive and expire?

Build that structure element by element. Watch which values get evicted and which survive.

The deque you just built maintains a monotonic decreasing sequence of values from front to back. This is not a coincidence --- it is the invariant that makes the whole structure work.

But before you see the code, think about what the deque actually stores. You saw elements getting evicted and surviving --- but what data type sits inside the deque?

Now the mechanics make sense. Picture a VIP queue at a concert. The person at the front is the tallest. When a new person arrives who is taller than the people at the back, those shorter people leave --- they will never be the tallest in any future window. The new person takes their place. And when the person at the front has been standing there too long (their index falls outside the window), they leave too.

Mechanically, the deque enforces two operations:

Back-pop (maintain monotonicity): When a new element arrives that is bigger than the back of the deque, the back is dominated. It can never be the max of any future window, because the new element entered later (so it will be in the window at least as long) and is bigger. Pop all dominated elements from the back. Then push the new element.

Front-pop (expire old elements): When the element at the front of the deque falls outside the current window boundary (its index is less than right - k + 1), it has expired. Pop it from the front.

After both operations, the front of the deque is always the current window maximum. No scanning required.

Here is the code for LC 239 (Sliding Window Maximum):

function maxSlidingWindow(nums: number[], k: number): number[] {

  const deque: number[] = [];  // stores indices, not values

  const result: number[] = [];

  for (let i = 0; i < nums.length; i++) {

    // Expire: front is outside the window

    if (deque.length && deque[0] < i - k + 1) {

      deque.shift();

    }

    // Monotonicity: pop smaller elements from back

    while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {

      deque.pop();

    }

    deque.push(i);

    if (i >= k - 1) {

      result.push(nums[deque[0]]);

    }

  }

  return result;

}

A critical detail: the deque stores indices, not values. This is the only way to know when the front element has left the window. If you stored values, you could not distinguish between two occurrences of the same number --- and you would not know which one to expire.

The inner while loop might look expensive --- in the worst case, it pops every element from the deque. Before you see the analysis, make a prediction:

Each index enters the deque exactly once (when it is pushed). Each index leaves the deque exactly once (either popped from the back because a larger element arrived, or popped from the front because it expired). Across the entire array of n elements, the total number of push operations is n, and the total number of pop operations is at most n. So the while loop, across all iterations of the outer for loop, runs at most n times total.

It is the same argument that makes the variable-size sliding window O(n): each element enters and leaves exactly once. The deque version is no different --- it just uses a deque instead of a left pointer to track which elements are “in the window.”

Think of it as a credit scheme. Every element gets one credit when it enters the deque. That credit pays for its eventual removal. No element is ever removed twice. So the total work is proportional to the number of elements, not the number of windows times the window size.

The monotonic deque is the last major data structure in the sliding window toolkit. Sums use arithmetic. Frequency maps use hash maps. And now, extrema (max/min) use monotonic deques. These three state-tracking mechanisms cover virtually every sliding window problem you will encounter.