p95 — Sliding Window Maximum

Source: LeetCode 239 · Hard · Topics: Deque, Monotonic Queue, Sliding Window Companies (2024–2025): Amazon (high), Google (medium), Meta (medium), Bytedance (high) Loop position: The canonical monotonic-deque problem. Required to articulate why a monotonic deque achieves O(n) where a heap achieves O(n log n).

1. Quick Context

Given array nums and window size k, return the max of every size-k window.

Solutions:

1. Brute: O(n·k). Recompute max per window.
2. Heap with lazy deletion: O(n log k). Push (-val, idx); pop top while stale.
3. Monotonic decreasing deque: O(n). Deque stores indices, values strictly decreasing from front to back.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/sliding-window-maximum/

STOP. 30-min timer.

3. Prerequisite Concepts

• collections.deque push/pop from both ends.
• Monotonic stack (LC 84, 496).
• Amortized analysis.

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Max of every length-k window.

3. Examples: [1,3,-1,-3,5,3,6,7], k=3 → [3,3,5,5,6,7].

5. Brute: O(n·k).

6. Target: O(n).

7. Pattern: Monotonic deque.

8. Develop: see solution.py.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 Monotonic deque invariant

Deque stores indices i_1 < i_2 < ... < i_m such that nums[i_1] > nums[i_2] > ... > nums[i_m] (strictly decreasing). Front is always the max of the current window.

Per element i:

1. Pop from back while nums[back] <= nums[i] (back can never be the max if a later equal-or-greater value exists).
2. Pop from front while front <= i - k (out of window).
3. Push i.
4. If i >= k - 1, record nums[deque[0]].

6.2 Why O(n) amortized

Each index is pushed once and popped at most once → 2n deque operations total.

6.3 Why heap is O(n log k), not O(n)

Heap doesn’t support efficient deletion of arbitrary elements. Lazy deletion is the workaround: keep popping stale top entries. Each push/pop is O(log k); each element pushed once and lazy-popped at most once.

6.4 Variants

• Sliding minimum: flip comparison; monotonic increasing deque.
• Both min and max: maintain two deques.
• Sliding median: harder; requires balanced BST or two heaps; O(n log k).
• Sliding k-th order statistic: order-statistics tree.

6.5 Family: monotonic stack/queue

• LC 239 Sliding Window Max (this).
• LC 84 Largest Rectangle in Histogram.
• LC 496 Next Greater Element.
• LC 862 Shortest Subarray with Sum ≥ K (monotonic deque on prefix sums).
• LC 1438 Longest Subarray with Absolute Diff ≤ Limit (two monotonic deques).

7. Anti-Pattern Analysis

1. Brute O(n·k) — Junior signal; fine on tiny n but flagged.
2. Heap without lazy deletion — incorrect (stale entries linger).
3. Store values not indices in deque — can’t tell when something falls out of window.
4. Use < not <= when popping back — for duplicates either works for max but <= keeps deque smaller.
5. Use > instead of >= when checking out-of-window — off-by-one; condition is front <= i - k.
6. Forget the i >= k - 1 guard before recording output.

8. Skills & Takeaways

• Monotonic deque pattern.
• Amortized linear via push/pop accounting.
• Heap with lazy deletion as alternative.

9. When to Move On

• Implement monotonic deque cold in 15 min.
• Explain amortized O(n).
• Cite LC 862, LC 1438 as deeper monotonic-deque problems.

10. Company Context

• Amazon: L5/L6; very common.
• Google: L5.
• ByteDance: loves monotonic deque.

Strong: “Monotonic decreasing deque of indices; front is the window max. Pop back while ≤ new, pop front when out-of-window. Each index touched twice → O(n).”

11. Interviewer’s Lens

12. Level Delta

• Mid (L4): Heap O(n log k).
• Senior (L5): Monotonic deque cold.
• Staff (L6): + amortized argument + cites LC 862 prefix-sum + monotonic deque.
• Principal (L7+): + framing as incremental order-statistic maintenance + connection to streaming-percentile sketches (P², GK) for harder variants.

13. Follow-up Q&A

Q1: Sliding minimum. A1: Symmetric; pop back while >= new.

Q2: Sliding median. A2: Two-heap balanced approach with lazy deletion, OR SortedList (skiplist), OR an order-statistics tree. O(n log k).

Q3: Window of dynamic size. A3: Two-pointer + monotonic deque still works.

Q4: Streaming (online) max with arbitrary window age cutoffs. A4: Sliding-window aggregation via monotonic deque; for time-based windows, deque of (timestamp, value).

Q5: Max of any subarray of size ≥ k. A5: Monotonic deque again, but record max once entered window.

14. Solution Walkthrough

See solution.py:

• max_sliding_window_deque — monotonic deque O(n).
• max_sliding_window_heap — heap + lazy deletion.
• max_sliding_window_brute — O(n·k) oracle.

15. Beyond the Problem

Principal code review: “Sliding Window Maximum is the canonical monotonic-deque problem, and the Staff+ recognition is that the pattern — ‘maintain a monotone-ordered structure of indices/values, evicting from one end as the window slides’ — appears everywhere in production. It’s the algorithm behind real-time bid-ask queries in trading systems, windowed top-K computations in streaming analytics (Flink, Spark Structured Streaming use specialized operators built on this), rate-limiter sliding-window-max-burst implementations, and monitoring systems (Prometheus’s max_over_time uses an equivalent structure). The deeper lesson is amortized analysis via the credit method: every element pays O(1) to enter the deque, and that credit covers its eventual eviction — same accounting used in two-pointer problems, KMP, and union-find with path compression. Once you internalize ‘each element does O(1) amortized work across the entire algorithm’, you stop being scared of nested-loop-looking code that’s actually linear. The principal-level extension: when the operation is not just max but any associative function (sum, gcd, matrix-multiply), use the ‘two-stack queue’ trick to get amortized O(1) per query; this is the building block for batched streaming aggregations in production data pipelines.”