Sliding Window Maximum (Deque) Explained: Tracing [1, 3, -1, -3, 5, 3, 6, 7]

Imagine you are tracking trends over a rolling three-day window given by nums = [1, 3, -1, -3, 5, 3, 6, 7] with $k=3$. Your goal is to find the maximum value inside every contiguous block of length 3. For the first window $\{1,3,-1\}$, the max is 3. As the window slides one step right to $\{3,-1,-3\}$, the max is still 3. But what happens if you simply run a fresh scan or a nested loop for every single shift?

If you inspect every element from scratch for each window, you end up repeatedly comparing values you have already evaluated. With an array of size $n$ and a window size $k$, a brute-force approach requires checking $k$ elements across $n-k+1$ windows, leading to an $O(n\cdot k)$ time complexity. When $n$ grows to millions and $k$ is large, that redundant scanning chokes performance.

We need a way to slide our view across nums = [1, 3, -1, -3, 5, 3, 6, 7] with $k=3$ such that we never re-scan elements we have already processed. The solution requires tracking candidates dynamically so that finding the maximum of the current window takes $O(1)$ amortized time.

To beat the $O(k)$ per window bottleneck, we need a data structure that drops elements we no longer care about before we even look at them again. Think of the deque not as a simple FIFO queue or stack, but as a decreasing tournament ladder of candidates. For our locked working example $\text{nums}=[1,3,-1,-3,5,3,6,7]$ and $k=3$, we maintain a doubly-ended queue (deque) storing array indices, not values.

Two invariant rules govern this deque at every step $i$:

1. Maintain Monotonicity (Tail Eviction): Before adding the current index $i$, we inspect the tail of the deque. If the value at the tail index ($\text{nums}[\text{tail}]$) is less than the incoming value ($\text{nums}[i]$), that tail element can never be the maximum of the current window or any future window that includes $i$. We pop it from the tail.
2. Enforce Window Bounds (Head Eviction): Indices that fall outside the current window window range $[i-k+1,i]$ are stale. We peek at the head of the deque; if its index is less than or equal to $i-k$, it has slid out of view and we pop it from the head.

By keeping the deque strictly decreasing from head to tail, the absolute maximum of the current window is always sitting safely at the head of the deque. We never search; we just read the front.

Let us trace the algorithm step by step using our locked example: nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3. We maintain a deque of indices holding values in strictly decreasing order. As the window slides from left to right, we clean out-of-bounds indices from the front and smaller elements from the back.

Given

- nums = [1, 3, -1, -3, 5, 3, 6, 7]
- k = 3
- Expected Result: [3, 3, 5, 5, 6, 7]

Steps & Intermediate States

- i = 0, value = 1: Deque is empty. Push index 0.
- Deque indices: [0], values: [1]
- i = 1, value = 3: Back of deque has 1 ($nums[0]<3$). Pop index 0. Push index 1.
- Deque indices: [1], values: [3]
- i = 2, value = -1: Back of deque has 3 ($nums[1]>-1$). Push index 2. Window size reached ($k=3$). Record front nums[1] = 3.
- Deque indices: [1, 2], values: [3, -1], Output so far: [3]
- i = 3, value = -3: Back of deque has -1 ($nums[2]>-3$). Push index 3. Front is 1 ($1
ot\le 3 - 3$), still in bounds. Record front nums[1] = 3.
- Deque indices: [1, 2, 3], values: [3, -1, -3], Output so far: [3, 3]
- i = 4, value = 5: Back elements -3, -1, 3 are all smaller than 5. Pop all from back. Push index 4. Front index 1 is now out of bounds ($1\le 4-3$), pop from front.
- Deque indices: [4], values: [5], Output so far: [3, 3, 5]
- i = 5, value = 3: Back has 5 ($nums[4]>3$). Push index 5. Record front nums[4] = 5.
- Deque indices: [4, 5], values: [5, 3], Output so far: [3, 3, 5, 5]
- i = 6, value = 6: Back elements 3, 5 are smaller than 6. Pop both. Push index 6. Record front nums[6] = 6.
- Deque indices: [6], values: [6], Output so far: [3, 3, 5, 5, 6]
- i = 7, value = 7: Back has 6 ($nums[6]<7$). Pop 6. Push index 7. Front index 6 is within bounds ($6\le 7-3$ is false, wait: $6\le 4$ is false, so front 6 is out of bounds ($6\le 4$ is false? Let's check: $i-k=7-3=4$. Front index 6 is $>4$, so it is in bounds). Record front nums[7] = 7.
- Deque indices: [7], values: [7], Final Output: [3, 3, 5, 5, 6, 7]

Result

The resulting window maximum array matches our expected output: [3, 3, 5, 5, 6, 7].

Now that you have traced the original setup nums = [1, 3, -1, -3, 5, 3, 6, 7] with $k=3$, let us test your mastery of the monotonic invariant with a slight parameter shift.

Imagine we run the same sliding window maximum algorithm on the same input array nums = [1, 3, -1, -3, 5, 3, 6, 7], but we change the window size to $k=4$. As the window expands across the array, elements enter and leave the deque to maintain both the window boundaries and the decreasing order of values.

Consider the exact moment when the right pointer is at index $i=4$ (which holds the value 5). At this precise step, the window spans indices 1 through 4, covering the subarray [3, -1, -3, 5].

Work through the mechanics of the monotonic deque to answer the check question below without executing code.

nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 4
# At i = 4 (value 5), what are the contents of the deque (storing indices)?
# Deque indices = ?

Having mastered the monotonic deque mechanics for our locked example nums = [1, 3, -1, -3, 5, 3, 6, 7] with k = 3, we can recognize how this exact structural invariant solves other streaming maximum queries. The core pattern of maintaining a double-ended queue of indices in decreasing order relies entirely on two conditions: elements leaving the window from the left must be pruned by index, and elements smaller than a new arrival must be pruned from the right because they can never be the maximum again while the new arrival is present.

Consider a variation where you need to find the sliding window minimum instead of the maximum for the exact same array and window size. By simply flipping the comparison operator from nums[tail] < nums[i] to nums[tail] > nums[i], the deque stores elements in increasing order, instantly yielding the minimum of every window with $O(n)$ total time complexity.

Similarly, this pattern generalizes to any sliding window query where you need to find the extreme value of a dynamic set while older elements expire in strict FIFO order. Whenever a brute-force approach forces redundant recalculations across overlapping ranges, look for monotonicity.

Suppose you are tasked with finding the sliding window maximum for a continuous data stream where elements arrive one by one, and instead of a fixed size $k$, the window is defined by a time threshold (e.g., all elements within the last 3 time units). Explain how you would adapt the index-based pruning step of our monotonic deque to handle timestamp expiration rather than fixed-index distance.