vizlearn

Sliding window maximum

Interview QuestionsBy Updated

Keep a deque of indices whose values are decreasing. When a new value arrives, everything smaller behind it is discarded — those can never be a maximum again, because the newcomer is bigger and outlives them. The front is always the current window's maximum. O(n) total.

Overview

The observation that does the work

If a[j] comes before a[i] and a[j] ≤ a[i], then a[j] can never be the maximum of any future window — every window containing it from now on also contains the bigger, later a[i]. So it can be thrown away the moment a[i] arrives.

What survives is a decreasing sequence, and its front is the maximum of the current window by construction. No scan is ever needed.

Lists & arraysCoding problemHard

Step through it

What to watch

  • Smaller values behind a larger one are discarded immediately.
  • The front is the answer without any scanning.
  • Indices are stored, not values — that is how expiry is detected.

Say this out loud

"Monotonic deque of indices, values decreasing. A new value evicts everything smaller from the back, because they can never win again. The front is the answer, and I drop it once it falls out of the window. Every index is pushed and popped once, so O(n)."

Sliding window maximum

Return the maximum of every window of size k as it slides along the array.

Why indices rather than values

The front must be discarded once it falls out of the window, and that needs its position. Storing values leaves no way to tell an expired maximum from a current one.

The expiry check is dq[0] <= i - k — the front is older than the window's left edge. This is the other place an off-by-one lives, and it is worth writing out the first window's indices to check it.

Why it is O(n), not O(n·k)

The inner while can pop several entries in one iteration, which looks quadratic. But each index is pushed exactly once and popped at most once across the entire run, so the total pops are bounded by n.

The alternatives are worth naming: recomputing max per window is O(n·k), and a heap is O(n log k) and needs lazy deletion because you cannot remove an arbitrary element. The deque beats both.

Run it in Python

The deque version with its total push and pop counts against the recompute-every-window version, on an input sized to make O(n) against O(n·k) unmistakable.

window_max.pyPython 3
Output
How the code works
  1. while dq and values[dq[-1]] <= v: dq.pop()The eviction. Anything smaller sitting behind a newer, larger value is permanently useless, because every future window holding it also holds the newcomer.
  2. dq[0] <= i - kExpiry by position, which is why indices are stored rather than values. Storing values leaves no way to tell a stale maximum from a live one.
  3. out.append(values[dq[0]])No scan. The deque is decreasing by construction, so its front is the window maximum — that is the entire payoff.
  4. pushes and popsEach index enters once and leaves at most once, so the totals are bounded by n however aggressive the inner loop looks. That is the amortised argument, measured.
Change one thing
  • Set k = 1. The deque never holds more than one entry and the answer is the input — a good sanity check on the expiry condition.
  • Change <= to < in the eviction. Equal values are now kept, which is still correct and grows the deque for no benefit.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. Why can a smaller value behind a larger one be discarded?
  2. Why store indices in the deque rather than values?
  3. The algorithm is O(n) rather than O(n·k) because:





 Cheat sheet
Sliding window maximum
Keep a deque of indices whose values are decreasing. When a new value arrives, everything smaller behind it is discarded — those can never be a maximum again, because the newcomer is bigger and outlives them. The front is always the current window's maximum. O(n) total.
INTERVIEW · vizlearn.in/interview/sliding-window-maximum.html
More in Interview
Interviewlist vs tuple vs deque vs array — which and why?InterviewHow does a Python dict work?InterviewWhy must dictionary keys be hashable?InterviewCount things with a dictionary
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact