—
You're given an array and a window of size k sliding left to right. Return the maximum inside each window. The naive scan is O(n·k); the elegant answer is a monotonic deque that runs in O(n). This module breaks down why.
Given nums = [1,3,-1,-3,5,3,6,7] and k = 3, the window starts over the first 3 elements and slides one step at a time. At each position we want the max:
[1 3 -1] → max 3[3 -1 -3] → max 3[-1 -3 5] → max 5[3,3,5,5,6,7]There are n - k + 1windows. Recomputing the max from scratch each time costs O(k) per window — that's the trap.
Keep a double-ended queue of indices whose corresponding values are strictly decreasing from front to back. Two invariants do all the work:
nums[j] ≤ nums[i] and j < i, then j can never be the maximum of any window that also contains i. A newer, bigger element makes the older smaller one useless. So we discard it forever.That single observation is what collapses O(n·k) into O(n): every index enters the deque once and leaves at most once.
For each index ias the window's right edge advances:
deque[0] ≤ i - k), drop it.nums[i], pop it. Maintains the decreasing order.i onto the back.i ≥ k-1 (first full window reached), nums[deque[0]]is this window's max.A heap of (value, index) also works and is a great thing to mention in an interview — but lazy deletion of expired entries pushes it to O(n log n) time and O(n) space. The deque dominates it. Knowing both, and being able to say why the deque wins, is the senior-level answer.
1function maxSlidingWindow(nums: number[], k: number): number[] {2▶ const result: number[] = [];3▶ const deque: number[] = []; // stores INDICES; values decreasing front→back45 for (let i = 0; i < nums.length; i++) {6 // 1 · evict the front if it has slid out of the window7 if (deque.length && deque[0] <= i - k) {8 deque.shift();9 }10 // 2 · drain the back of all values ≤ the incoming value11 while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {12 deque.pop();13 }14 // 3 · push the current index15 deque.push(i);16 // 4 · record the max once the first window is complete17 if (i >= k - 1) {18 result.push(nums[deque[0]]);19 }20 }21 return result;22}
function maxSlidingWindow(nums: number[], k: number): number[] {
const result: number[] = [];
const deque: number[] = []; // stores INDICES; values decreasing front→back
for (let i = 0; i < nums.length; i++) {
// 1 · evict the front if it has slid out of the window
if (deque.length && deque[0] <= i - k) {
deque.shift();
}
// 2 · drain the back of all values ≤ the incoming value
while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
deque.pop();
}
// 3 · push the current index
deque.push(i);
// 4 · record the max once the first window is complete
if (i >= k - 1) {
result.push(nums[deque[0]]);
}
}
return result;
}result collects answers; deque holds indices (a plain array used as a deque via shift/pop/push). The values those indices point to stay in decreasing order.i is [i-k+1, i]. If the front index is ≤ i-kit's outside that window, so we shift() it off. Only one element can expire per step, so an if suffices (no loop needed).nums[i]is dominated and gets popped. This is the heart of the trick — it's what guarantees the deque stays decreasing and the front stays the true max.i. It's now the smallest value at the back (everything ≤ it is gone), preserving the invariant.i ≥ k-1. From then on, every step emits exactly one answer: nums[deque[0]].while looks like it could be O(k), but across the whole run each index is pushed once and popped at most once. Total work is bounded by 2n operations ⇒ O(n).>= — keep an increasing deque. Same structure.(value,index) with lazy eviction → O(n log n). The deque is strictly better; naming the tradeoff is the point.k === 1 (result equals input), k === nums.length (single max), empty input. The code handles all three without special-casing.if on line 7 but a whileon line 11?" At most one index expires per advance (front), but many can be dominated at once (back). A favorite gotcha.function maxSlidingWindow(nums: number[], k: number): number[] {
const result: number[] = [];
const deque: number[] = []; // stores INDICES; values decreasing front→back
for (let i = 0; i < nums.length; i++) {
// 1 · evict the front if it has slid out of the window
if (deque.length && deque[0] <= i - k) {
deque.shift();
}
// 2 · drain the back of all values ≤ the incoming value
while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
deque.pop();
}
// 3 · push the current index
deque.push(i);
// 4 · record the max once the first window is complete
if (i >= k - 1) {
result.push(nums[deque[0]]);
}
}
return result;
}while looks like it could be O(k), but across the whole run each index is pushed once and popped at most once. Total work is bounded by 2n operations ⇒ O(n).A binary heap of [value, index] pairs always exposes the global maximum at its top — discard any top whose index has slid out of the window before trusting it.
function maxSlidingWindow(nums: number[], k: number): number[] {
const result: number[] = [];
// Max-heap of [value, index], ordered by value descending.
const heap = new MaxHeap();
for (let i = 0; i < nums.length; i++) {
heap.push([nums[i], i]);
// Lazily evict any top whose index is no longer in [i-k+1, i].
while (heap.peek()![1] <= i - k) {
heap.pop();
}
if (i >= k - 1) {
result.push(heap.peek()![0]);
}
}
return result;
}
// A binary max-heap of [value, index] pairs, ordered by value.
class MaxHeap {
private data: Array<[number, number]> = [];
size(): number {
return this.data.length;
}
peek(): [number, number] | undefined {
return this.data[0];
}
push(pair: [number, number]): void {
this.data.push(pair);
this.bubbleUp(this.data.length - 1);
}
pop(): [number, number] | undefined {
const n = this.data.length;
if (n === 0) return undefined;
const top = this.data[0];
const last = this.data.pop()!;
if (n > 1) {
this.data[0] = last;
this.bubbleDown(0);
}
return top;
}
private bubbleUp(i: number): void {
while (i > 0) {
const parent = (i - 1) >> 1;
if (this.data[parent][0] >= this.data[i][0]) break;
[this.data[parent], this.data[i]] = [this.data[i], this.data[parent]];
i = parent;
}
}
private bubbleDown(i: number): void {
const n = this.data.length;
for (;;) {
const left = 2 * i + 1;
const right = 2 * i + 2;
let largest = i;
if (left < n && this.data[left][0] > this.data[largest][0]) largest = left;
if (right < n && this.data[right][0] > this.data[largest][0]) largest = right;
if (largest === i) break;
[this.data[largest], this.data[i]] = [this.data[i], this.data[largest]];
i = largest;
}
}
}n items. The log nfactor on every push/pop is exactly what the monotonic deque eliminates, but the heap version generalizes cleanly to "k largest in window" style follow-ups.For every one of the n - k + 1 windows, walk its k elements and keep the largest. No auxiliary structure — the obvious first answer.
function maxSlidingWindow(nums: number[], k: number): number[] {
const result: number[] = [];
// There are n - k + 1 windows, each starting at index `start`.
for (let start = 0; start + k <= nums.length; start++) {
let windowMax = nums[start];
for (let j = start + 1; j < start + k; j++) {
if (nums[j] > windowMax) {
windowMax = nums[j];
}
}
result.push(windowMax);
}
return result;
}O(n·k). For large k (say k ≈ n/2) this is effectively quadratic and times out — fine as a warm-up answer you then improve.| "max/min of every sliding window" | monotonic deque of indices |
| need O(1) window extremum | front of the deque = answer |
| newer element ≥ older one | pop the dominated back |
| front index slid out of window | shift it off (deque[0] ≤ i-k) |
const result: number[] = [];
const deque: number[] = []; // indices, values decreasing
for (let i = 0; i < nums.length; i++) {
if (deque.length && deque[0] <= i - k) deque.shift(); // retire old front
while (deque.length && nums[deque.at(-1)!] <= nums[i]) // kick out weak back
deque.pop();
deque.push(i);
if (i >= k - 1) result.push(nums[deque[0]]); // front = max
}
return result;nums[back] ≤ nums[i]?if to evict the front, but line 11 uses a while to drain the back. Why the difference?nums=[7,2,4], k=2, what is the result?