Stage 1 · Code
Two Pointers, Sliding Windows & Deques
Monotonic Deque for Window Extremes
A queue that forgets expired indices and permanently weaker candidates can report every sliding-window maximum in linear time.
The Deque Invariant
A normal fixed window can maintain a sum by subtracting one value and adding another. A maximum is harder: when the current maximum leaves, the next maximum might be anywhere inside the window. Re-scanning all k values makes the solution O(n·k). A monotonic deque avoids that scan by retaining only values that can still become the maximum now or in a future overlapping window.
Indices increase from front to back because new elements arrive on the right. Their values decrease from front to back, so the front index always names the largest value still eligible for the active window.
The deque is not a sorted copy of the window. It is a shortlist of undefeated candidates. If a newer value is greater than or equal to an older value, the older one can never win again: every future window containing the older index also contains the newer index until the older index expires first. Removing that dominated candidate is safe, not heuristic.
| Deque property | What it guarantees | Where it is used |
|---|---|---|
| Indices increase front → back | The oldest candidate is at the front | Expiry checks |
| Values decrease front → back | The largest candidate is at the front | Reading the answer |
| Only undominated indices remain | No stored candidate is provably useless | Linear total work |
Two Kinds of Eviction
Every iteration performs two logically different cleanups. First, expiry eviction removes indices from the front when they are left of right-k+1. Those elements may still be large, but they are no longer inside the current window. Second, dominance eviction removes indices from the back while their values are less than or equal to the incoming value. Those elements are still inside the window, but they can no longer be the best candidate.
| Eviction | Test | End of deque | Reason |
|---|---|---|---|
| Expiry | index < window left boundary | Front | Candidate is outside the window |
| Dominance | stored value ≤ incoming value | Back | Newer candidate is at least as strong and lives longer |
With duplicates, keeping the newer equal value is enough. It produces the same maximum and expires later, so the older duplicate has no future window in which it is uniquely useful. Using ≤ keeps the deque compact; using < is also correct but retains older equals.
Worked State Trace
Trace nums = [1, 3, -1, -3, 5, 3, 6, 7] with k = 3. The table shows deque entries as index:value after both evictions and the append. An answer is emitted only after the first complete window exists.
| right / value | Active window | Deque after update | Emitted maximum |
|---|---|---|---|
| 0 / 1 | not full | [0:1] | — |
| 1 / 3 | not full | [1:3] (1 dominates 0) | — |
| 2 / -1 | [1, 3, -1] | [1:3, 2:-1] | 3 |
| 3 / -3 | [3, -1, -3] | [1:3, 2:-1, 3:-3] | 3 |
| 4 / 5 | [-1, -3, 5] | [4:5] (1 expires; 5 dominates 2 and 3) | 5 |
| 5 / 3 | [-3, 5, 3] | [4:5, 5:3] | 5 |
| 6 / 6 | [5, 3, 6] | [6:6] (6 dominates 4 and 5) | 6 |
| 7 / 7 | [3, 6, 7] | [7:7] (7 dominates 6) | 7 |
At right = 4, expiry and dominance happen for different reasons. Index 1 is removed because the new window starts at index 2. Indices 2 and 3 are then removed because value 5 is larger and newer. Keeping those reasons separate makes off-by-one bugs much easier to diagnose.
Go 1.26+ Implementation
Complexity and Edge Cases
The nested loops do not make the algorithm quadratic. Each index is appended exactly once. After that, it can be removed at most once: either from the front when it expires or from the back when a newer value dominates it. Across the entire input there are at most n appends and n removals, so the total time is O(n). The deque stores at most k indices, and the returned answer stores n-k+1 values.
- k <= 0: there is no meaningful window, so the function returns an empty non-nil slice.
- k > len(nums): no complete window exists, so the function returns an empty slice instead of allocating with a negative capacity.
- Empty input: returns an empty slice.
- k == 1: every element is its own maximum, so the result equals nums by value.
- Duplicates: dominance eviction uses <=, retaining the newest equal maximum because it expires later.
- Strictly decreasing input: no dominance eviction occurs; expiry removes one old maximum per slide.
Expiry is positional. If the deque contains only values, duplicate maxima make it ambiguous which occurrence left the window. Indices preserve both value lookup and lifetime.
Problems
Quiz
Why does Sliding Window Maximum store indices instead of only values?
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.