ASAPUtils
The signal
“Maximum of every window of size k.” A heap gets you O(n log k) and is a perfectly respectable answer. Getting to O(n) requires one observation about what you’re allowed to permanently discard.
Approach ladder
1. Brute force — O(n · k)
Recompute the max of each window from scratch. At n = 10⁵ and k = 10⁴ that’s 10⁹ operations.
2. Heap — O(n log k)
Push each element, pop stale ones lazily from the top. Genuinely good, and what most people land on.
3. The insight
Consider two indices i < j, both inside the window, with a[i] <= a[j].
a[i] can never be the answer again. Any future window containing i also contains j —
because j is to the right and windows only move right — and a[j] is at least as big. So a[i]
is permanently useless and can be deleted, not just skipped.
Apply that rule continuously and what remains is a sequence of indices whose values strictly decrease. The front is always the current maximum.
4. Optimal — monotonic deque, O(n)
Three moves per step:
- Evict the front if it has fallen out of the window (
dq.front() <= r - k). - Pop from the back while
a[back] <= a[r]— those are the permanently-useless ones. - Push
r, then reada[dq.front()]as this window’s maximum.
vector<int> maxSlidingWindow(vector<int>& a, int k) {
deque<int> dq; // indices; values decrease front → back
vector<int> res;
for (int r = 0; r < (int)a.size(); r++) {
while (!dq.empty() && dq.front() <= r - k) dq.pop_front();
while (!dq.empty() && a[dq.back()] <= a[r]) dq.pop_back();
dq.push_back(r);
if (r >= k - 1) res.push_back(a[dq.front()]);
}
return res;
}
function maxSlidingWindow(a, k) {
const dq = []; // indices; values decrease front → back
const res = [];
let head = 0; // index pointer — NOT shift(), which is O(n)
for (let r = 0; r < a.length; r++) {
while (head < dq.length && dq[head] <= r - k) head++;
while (head < dq.length && a[dq[dq.length - 1]] <= a[r]) dq.pop();
dq.push(r);
if (r >= k - 1) res.push(a[dq[head]]);
}
return res;
}
Why indices and not values
You need to know when an element falls out of the window, and only its index tells you that. Store values alone and you can’t tell whether the front is still in range.
Why it’s O(n)
Each index is pushed exactly once and popped at most once. The inner while may run many times on
a single iteration, but summed across the whole run it can’t exceed n pops.
This is the amortised argument, and it’s the third time it’s appeared — Longest Consecutive Sequence, the sliding window itself, and now here. In week 3 the monotonic stack uses exactly the same reasoning. Learning to state it is the real takeaway from this problem.
Walkthrough
[1,3,-1,-3,5,3,6,7], k = 3:
| r | value | deque (as values) | emitted |
|---|---|---|---|
| 0 | 1 | [1] | — |
| 1 | 3 | [3] (1 popped: ≤ 3) | — |
| 2 | −1 | [3, −1] | 3 |
| 3 | −3 | [3, −1, −3] | 3 |
| 4 | 5 | [5] (all popped) | 5 |
| 5 | 3 | [5, 3] | 5 |
| 6 | 6 | [6] | 6 |
| 7 | 7 | [7] | 7 |
Traps
shift()in JavaScript. O(n) per call; silently makes the solution quadratic. Use a head index.- Storing values instead of indices. You lose the ability to evict.
- Evicting after pushing. Do the front eviction first, based on
r - k. - Emitting before the window is full. Only from
r >= k - 1.
Blank re-solve prompt
Return the maximum of every window of size k in O(n). Then state, in one sentence, why the inner while loop doesn’t make it quadratic.