Monotonic Queue Interview Questions: Sliding Maxima, Expiry, and Amortized Cost

Monotonic queue interview questions are rarely about memorizing a deque template. The real test is whether you can explain why an index remains useful, when it expires, how equal values affect tie behavior, and why a nested while loop still costs linear time. For a fixed-width sliding maximum, the deque stores indexes in increasing time order while their values decrease from front to back. The front is therefore the maximum among candidates that are both active and unbeaten.

Start with Return the Maximum of Every Sliding Window if you want the direct problem. This guide focuses on the interview follow-ups: deriving both removal rules, tracing index lifetimes, choosing a duplicate policy, adapting the invariant to minimums and bounded dynamic programming, and proving the amortized bound.

Monotonic Queue Interview Questions: Quick Answer

Store indexes, not only values. Before adding index i, remove any front index < i - k + 1 because it is outside the active window. Then remove back indexes whose values are <= nums[i]; the new value is at least as large, remains active longer, and makes those older candidates useless. Append i. Once i >= k - 1, report nums[dq[0]].

The two ends have different jobs. The front handles expiry by age. The back handles domination by value and lifetime. Mixing those rules is the source of most bugs. Each index is appended once and removed at most once, so all deque operations total O(n) even though one iteration may pop many indexes.

That complexity statement is a data-structure fact, not evidence that every sliding-window question requires a monotonic deque. A fixed-width sum needs only subtraction and addition; a window median needs order statistics; arbitrary deletions may require a balanced tree or heap strategy.

Derive the invariant from what the front must answer

For a maximum over the current window, dq[0] must identify the largest active value. Three conditions make that true:

Invariant	What it guarantees	How it is maintained
Indexes increase from front to back	Older candidates leave first	Append only the current index
Values decrease from front to back	The front is the maximum	Pop dominated indexes from the back
Every stored index is inside the window	The answer is eligible	Pop expired indexes from the front

The deque is not a copy of the window. It is a frontier of candidates that could still become the answer. If a new value x arrives at index i and an older back candidate j satisfies nums[j] <= x, then j can never win a future window containing both: x is no smaller and expires later. Removing j loses nothing.

That argument explains the usual <= pop condition. Using < is also correct for maximum values, but equal indexes remain in the deque. The choice changes tie behavior and memory shape. With <=, the newest equal maximum survives; with <, the oldest equal maximum survives until expiry. State which index you want if the task asks for positions, not just values.

Write the template in the same order you explain it

from collections import deque

def sliding_max(nums: list[int], k: int) -> list[int]:
    if not nums or k <= 0 or k > len(nums):
        return []

    dq = deque()  # indexes; values strictly decreasing front -> back
    out = []

    for i, x in enumerate(nums):
        left = i - k + 1
        while dq and dq[0] < left:
            dq.popleft()
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            out.append(nums[dq[0]])

    return out

The invalid-input behavior is an API decision. This version returns [] when k <= 0, k > n, or the input is empty. An interviewer may instead guarantee 1 <= k <= n or expect an exception. Settle the contract before coding so edge-case handling does not obscure the invariant.

Avoid saying “the deque is decreasing” without naming what decreases. Indexes increase because time moves forward. Values decrease because dominated backs are removed. Both orders coexist, and each supports a different operation.

Trace expiry and domination separately

Use nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3. The expected maxima are [3, 3, 5, 5, 6, 7].

i, value	Front expiry	Back domination	Deque after append (index:value)	Output
0, 1	none	none	[0:1]	—
1, 3	none	pop 0:1	[1:3]	—
2, -1	none	none	[1:3, 2:-1]	3
3, -3	none	none	[1:3, 2:-1, 3:-3]	3
4, 5	none	pop 3, 2, 1	[4:5]	5
5, 3	none	none	[4:5, 5:3]	5
6, 6	none	pop 5, 4	[6:6]	6
7, 7	none	pop 6	[7:7]	7

This trace emphasizes an easy-to-miss point: an index may disappear because it expired, or because a later index dominated it. Those are distinct proofs. Expiry says the index is no longer eligible. Domination says it is eligible now but can never win again.

Use [9, 1, 2, 3] with k = 3 to force the expiry path. At i = 3, the left boundary is one, so index zero must leave before the answer is read. If the code stores values only, it cannot tell whether the 9 at the front belongs to index zero or a later position.

The expiry inequality is the boundary contract

For a full window ending at i, the active indexes are [i - k + 1, i]. Therefore an index is expired exactly when

dq[0] < i - k + 1

Equivalent code may use dq[0] <= i - k. Both express the same boundary. Writing <= i - k + 1 removes the leftmost valid element one step early. Test k = 1; every new index should immediately become the only active candidate and produce its own value.

Order can be correct in more than one form, but the invariant must hold before reading the answer. Expire before reporting. If you report first and expire afterward, the previous window's maximum may leak into the current result. Back domination may occur before or after expiry when indexes are ordered, but expiring first keeps the two proofs visible and bounds the active state cleanly.

Duplicates decide which index represents the maximum

Consider nums = [5, 5, 4], k = 2:

Back pop rule	State after index 1	First output	Surviving representative
Pop <= x	[1:5]	5	Newest equal maximum
Pop < x	[0:5, 1:5]	5	Oldest equal maximum until expiry

Both return the same maximum values. They do not return the same argmax index. “Pop smaller elements” is therefore incomplete when duplicates exist. Ask whether ties should prefer the earliest or latest position, and match the comparison to that contract.

The newest-wins rule is often convenient because it discards more state: an equal newer value has a longer remaining lifetime. The oldest-wins rule is useful when the requested output must preserve earliest-index ties. Neither choice is universally superior.

Prove amortized O(n) without hand-waving

The inner loop can pop many indexes during one iteration. Worst-case cost for that single iteration is O(k), so calling every operation worst-case constant is false. The complete scan is linear because work is bounded across all iterations.

Give each index one token when it is appended. That index can leave only once: either from the back after being dominated or from the front after expiring. It cannot be removed twice. Across n arrivals there are exactly n appends and at most n removals. Front reads and boundary checks add constant work per iteration, so the total is O(n) and the amortized cost per arrival is O(1).

Space is O(k), not automatically O(n), because the deque contains only active indexes. A strictly decreasing window such as [9, 8, 7, 6] is the memory worst case: no candidate is dominated, so up to k indexes remain. A strictly increasing input is the pop-work stress case: each arrival removes the previous candidate, but the deque stays tiny.

Change the objective by changing the comparison

For a sliding minimum, retain increasing values and pop from the back while nums[dq[-1]] >= x. Expiry is unchanged because the window geometry did not change. The candidate dominance proof reverses: an older value no smaller than the new value cannot be a future minimum.

The candidate-reported Compute streaming sliding-window minimums uses a different output contract: it emits one minimum for every prefix, using a window of up to k items. The fixed-width maximum above emits only after the first complete window. A strong answer notices that output-count difference before reusing the template.

A monotonic deque also appears in bounded dynamic programming. If a recurrence asks for the best prior state among indexes j in [i-k, i-1], store candidate DP indexes, expire them by range, read the best at the front, compute dp[i], and then insert i while removing dominated states. The proof is the same, but the deque orders dp values rather than raw input values.

Know when the deque is the wrong tool

Query contract	Better tool	Why
Fixed-window sum or count	Running aggregate	Removal has an exact inverse
Fixed-window maximum or minimum	Monotonic deque	Only the unbeaten frontier matters
Sliding median or kth value	Two heaps or ordered multiset	The frontier does not preserve ranks
Arbitrary range maximum queries, no updates	Sparse table or segment tree	Windows are queried out of scan order
Arbitrary insertions and deletions	Balanced tree or indexed heap	Expiry is no longer FIFO by index

Do not confuse a monotonic queue with a monotonic stack. A stack answers nearest-greater or nearest-smaller relationships in a one-directional sweep. A window extremum must evict old indexes from the front, so it needs deque access at both ends. The existing Monotonic Stack Interview Pattern owns the neighbor-query intent; this article owns moving-window eligibility and expiry.

Diagnose failures with minimal counterexamples

Symptom	Minimal test	Likely bug
Old maximum survives too long	[9,1,2,3], k=3	Expiry happens after output or uses the wrong inequality
Duplicate argmax index is wrong	[5,5], k=2	Strictness does not match the tie contract
Cannot expire correctly	[2,1,2], k=2	Stored values instead of indexes
First answer appears too early	[4,2,1], k=3	Emitted prefix extrema instead of full-window extrema
Increasing input becomes quadratic	long increasing array	Removed from an array front or rebuilt the deque each step

Reproduce the smallest failure, identify whether it violates eligibility or dominance, and change one rule. That explanation is more useful than reciting the finished template because it shows you can recover under interview pressure.

Final takeaway

The strongest monotonic queue answer starts with candidate lifetime. Store indexes so the front can expire by age. Remove dominated candidates from the back because a newer equal-or-better value lasts longer. Read the extremum only after every remaining index is active. Then prove linear time by counting each index's single insertion and single removal across the whole scan.

Practice the standard maximum once, then change one requirement at a time: return argmax indexes with earliest ties, emit prefix minimums, or optimize over the last k DP states. Those variations force you to derive the invariant instead of copying a loop. Continue with the five linked Coding & Algorithms questions and explain the removal reason for every pop.

Sources and Further Reading

• CP-Algorithms: Minimum Stack / Minimum Queue
• Princeton COS 226: Stacks, Queues, Deques, and Steques

Technical sources support the data-structure behavior.*