239. Sliding Window Maximum

At a Glance

• Topic: sliding-window
• Pattern: Monotonic Deque / Stack (queue variant)
• Difficulty: Hard
• Companies: Amazon, Google, Bloomberg, Microsoft, Adobe
• Frequency: Very High
• LeetCode: 239

Problem (one-liner)

Given integer array numbers and window size windowSize, return the maximum value in each sliding window of length windowSize as the window moves from left to right.

Recognition Cues

• "Max/min in every subarray of fixed length K"
• Naive is O(n·k) — need amortized O(1) per step
• Same pattern as "next greater element" but time-indexed

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — rescan each window for max — O(n · windowSize) time / O(1) space.
• Acceptable — TreeMap / multiset (ceil/floor) maintaining counts — O(n log windowSize) time; simpler if deque APIs feel risky.
• Acceptable (engineering) — segment tree or sparse table for range max queries — O(n log n) preprocess + O(log n) per query; heavier than needed here.
• Optimal — monotonic deque of indices with decreasing values; pop expired from front, pop weaker candidates from back — O(n) time / O(windowSize) space.

Optimal Solution

Go

func maxSlidingWindow(numbers []int, windowSize int) []int {
	n := len(numbers)
	if n == 0 || windowSize == 0 {
		return []int{}
	}
	dequeIndices := make([]int, 0)
	result := make([]int, 0, n-windowSize+1)

	for index := 0; index < n; index++ {
		for len(dequeIndices) > 0 && dequeIndices[0] <= index-windowSize {
			dequeIndices = dequeIndices[1:]
		}
		for len(dequeIndices) > 0 && numbers[dequeIndices[len(dequeIndices)-1]] <= numbers[index] {
			dequeIndices = dequeIndices[:len(dequeIndices)-1]
		}
		dequeIndices = append(dequeIndices, index)
		if index >= windowSize-1 {
			result = append(result, numbers[dequeIndices[0]])
		}
	}
	return result
}

JavaScript

function maxSlidingWindow(numbers, windowSize) {
	const n = numbers.length;
	if (n === 0 || windowSize === 0) {
		return [];
	}
	const dequeIndices = [];
	const result = [];
	for (let index = 0; index < n; index++) {
		while (dequeIndices.length > 0 && dequeIndices[0] <= index - windowSize) {
			dequeIndices.shift();
		}
		while (
			dequeIndices.length > 0 &&
			numbers[dequeIndices[dequeIndices.length - 1]] <= numbers[index]
		) {
			dequeIndices.pop();
		}
		dequeIndices.push(index);
		if (index >= windowSize - 1) {
			result.push(numbers[dequeIndices[0]]);
		}
	}
	return result;
}

Walkthrough

numbers = [1,3,-1,-3,5,3,6,7], windowSize = 3

Invariant: deque indices have strictly decreasing numbers[index]; front is always max of current window.

Edge Cases

• windowSize == 1 → each element
• windowSize == n → single max
• Monotone increasing array → deque always last index
• Negative numbers — fine

Pitfalls

• Using shift() in JS in hot loop is O(windowSize) amortized per step on plain arrays — interview OK on LC; production uses index-head deque or ring buffer for strict O(n) total.
• Comparing <= vs < when popping from back — pick ≤ to drop duplicate smaller entries so duplicates remain represented once.

Similar Problems

• 739. Daily Temperatures — monotonic stack “next greater” (Medium stepping stone).
• 424. Longest Repeating Character Replacement — fixed/threshold window (Medium; different validity).
• 76. Minimum Window Substring — variable window Hard sibling.

Variants

• Min and max per window — maintain two monotonic deques (or one trick with delays).
• Dynamic window size — no longer fixed-K max; problem changes entirely.
• Count of elements > X per window — different structure (BST / buckets).

Mind-Map Tags

#sliding-window #monotonic-deque #fixed-k #amortized-O1 #queue-indices