-
Notifications
You must be signed in to change notification settings - Fork 0
050 — Sliding Window Maximum
LeetCode 239 · Hard. Given an array nums and a window size k, return an array of the maximum value in each contiguous window of size k as it slides from the left end of nums to the right end.
Picture a doorway with a "tallest person currently visible" sign above it, and a line of people walking past in single file, k people visible through the doorway at any moment. A naive doorman re-measures everyone currently visible every time the line shifts. A smarter doorman keeps a private lineup of "candidates who could still become the tallest" — and here's the trick: the instant a taller person walks in, every shorter candidate already in the private lineup can be dismissed permanently. They can never be the tallest again, because the new taller person is both younger (will leave the window later) and taller than them — they're strictly worse in every way from now on. So the private lineup only ever holds people in strictly decreasing height, front to back, and the front of that lineup is always the current tallest-visible person.
That private lineup — add to the back, remove dominated entries from the back, remove aged-out entries from the front — is a monotonic deque.
"Maximum in every window of size k" is a fixed-size window (Sliding Window's simplest form) paired with an aggregate (max) that's expensive to recompute from scratch at every slide. Whenever a fixed window needs a running max or min maintained across slides, that's the signal to reach for a monotonic deque: an index-based double-ended queue kept in strictly decreasing (for max) or increasing (for min) order of value, so the answer for the current window is always sitting at the front.
For every window position, scan all k elements inside it to find the max.
func maxSlidingWindowBruteForce(_ nums: [Int], _ k: Int) -> [Int] {
guard !nums.isEmpty, k > 0 else { return [] }
var result: [Int] = []
for start in 0...(nums.count - k) {
var windowMax = nums[start]
for i in start..<(start + k) {
windowMax = max(windowMax, nums[i])
}
result.append(windowMax)
}
return result
}Big-O: O(n · k) time — every one of the n - k + 1 windows is rescanned in full. O(1) extra space (excluding the output array).
Maintain a deque of indices, kept in strictly decreasing order of nums value. Before adding the current index, pop off any trailing indices whose values are beaten by it — they're now permanently dominated. Then evict the front index once it ages out of the window.
func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
guard !nums.isEmpty, k > 0 else { return [] }
var deque: [Int] = [] // holds indices; nums[deque[i]] is strictly decreasing left to right
var head = 0 // logical front pointer into `deque` — avoids Array's O(n) removeFirst()
var result: [Int] = []
for right in 0..<nums.count {
// Dismiss trailing candidates that the new value beats — they can
// never be the max of any future window once a bigger value is behind them.
while deque.count > head, nums[deque[deque.count - 1]] <= nums[right] {
deque.removeLast()
}
deque.append(right)
// Retire the front candidate once it has aged out of the window on the left.
if deque[head] <= right - k {
head += 1
}
if right >= k - 1 {
result.append(nums[deque[head]])
}
}
return result
}
// smoke test
print(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)) // [3, 3, 5, 5, 6, 7]
print(maxSlidingWindow([1], 1)) // [1]Big-O: O(n) time — each index is appended to the deque exactly once and removed (from either end) at most once across the entire run, so the total work across all n steps is linear, not O(n · k). O(k) space for the active portion of the deque (the head pointer trick above trades a small amount of unreclaimed array memory for guaranteed O(1) amortized operations, instead of paying Array.removeFirst()'s O(n) shifting cost — see the Queues & Deques chapter for a reusable O(1)-both-ends Deque<T> that avoids this trade-off entirely).
The brute force treats every window as an unrelated problem and rescans all k elements from zero, even though consecutive windows overlap in k - 1 positions. The optimal solution exploits a domination argument: if an earlier element is smaller than a later element within reach of the same future windows, the earlier one can never win — it will always either already be beaten by the later element, or age out of the window before the later one does. Discarding permanently-dominated candidates the instant they're recognized means the deque only ever holds "genuinely still-competitive" candidates, and its front is always the answer for the current window. Since every index is pushed once and popped at most once (from either end) over the whole algorithm, the total work is O(n) — the same "touch each element a constant number of times" guarantee that makes a Monotonic Stack linear.
- Sliding Window — the fixed-size window sliding across the array.
- Arrays & Strings — the array being scanned.
-
Queues & Deques — the monotonic deque of indices that makes the running max
O(1)to query. - Monotonic Stack — the same "each element discarded at most once" domination argument, applied here to a deque instead of a stack.
Sliding Window Maximum is a doorman's private lineup of still-possibly-tallest people — shorter candidates get dismissed the instant someone taller and younger shows up, so the front of the lineup is always today's tallest.
The deque never removes an index because a smaller value came before it — only because a later, bigger-or-equal value made it permanently irrelevant, or because it aged out of the window. Explain why an index whose value is smaller than a later index's value can never again be the answer for any future window, once that later index is inside the same window as it.
⬅️ Previous: Minimum Window Substring · Next: Valid Parentheses ➡️