How to Learn Monotonic Stack and Deque Algorithms: Dominance, Next-Greater Queries, Sliding Windows and Amortized O(n)

Wait, What?

The nested while-loop can run many times in one iteration and the whole algorithm can still be O(n).

Monotonic stacks and deques look deceptively simple: scan values, repeatedly discard candidates that can no longer matter, and keep the survivors in ordered form. The deeper idea is dominance. When a newer value makes an older value permanently irrelevant to every future answer, the older value can be removed immediately. That single idea powers next-greater-element problems, histogram boundaries, sliding-window extrema and some dynamic-programming optimisations.

This article owns the monotonic-candidate pattern. It does not replace the existing stack/queue foundations, range-query article or amortized-analysis article. Those remain canonical for their broader jobs. Here the learner sees how an invariant and a discard proof turn repeated comparison into one linear pass.

Quick Answer

Learn the pattern as brute-force comparison → define the candidate relation → state the monotonic invariant → prove why a popped candidate can never matter again → trace pushes and pops → derive O(n) by operation counting → extend from stack to deque when candidates can expire by age.

Beginner: Start With Next Greater Element

Suppose the array is [2, 1, 2, 4, 3] and we want the next strictly greater value to the right of every position. The obvious method scans rightward from each element. It is easy to understand and can take O(n²). Keep that method first, because the fast method only makes sense after the repeated wasted work is visible.

Now scan from right to left while keeping a stack of useful candidates. Before reading the answer for the current value x, pop every stack value that is less than or equal to x. Why is that safe? Because x is both closer to every future element on the left and at least as large as the discarded value. The discarded value has been dominated.

The Invariant Is More Important Than the Code

For a decreasing-candidate stack, write the invariant before writing the loop: “From bottom to top, the stored candidate values are strictly decreasing under the chosen equality rule, and every stored index remains capable of answering at least one future query.”

Then make the learner predict the stack after each input item. Code tracing research and PRIMM-style teaching both support the value of prediction and explanation before independent code production. The aim is not merely to reproduce a template; it is to know why each pop is irreversible and safe.

Equality Is a Specification Choice

“Next greater” and “next greater or equal” are different problems. The comparison inside the pop loop changes accordingly. With duplicates, < versus <= can change answers and boundary widths. Professional implementations should derive the comparison from the exact semantic contract instead of copying a memorised operator.

Intermediate: From Nearest Greater to Histogram Boundaries

For the largest rectangle in a histogram, each bar needs the nearest position to the left and right where a lower bar blocks its expansion. A monotonic stack discovers those boundaries while scanning. When a bar is popped, the current index often becomes one boundary and the new stack top becomes the other. This is a useful transfer test: the stack is no longer answering “what value comes next?” but the dominance invariant is the same.

Why the Nested Loop Is Still Linear

The inner while loop can pop many elements in one outer iteration. That does not make the total O(n²). Across the entire scan, each index is pushed once and can be popped at most once. So there are at most n pushes and n pops. This is aggregate amortized analysis: the expensive iteration spends work that previous cheap iterations made possible.

This distinction matters. Amortized O(1) per item is not average-case probability. It is a deterministic bound on total work over the sequence.

When a Stack Is Not Enough: Candidates Can Expire

Now consider the maximum of every window of width k. A candidate can become irrelevant for two independent reasons:

• Dominated: a newer value is at least as good and will outlive it. Remove from the back.
• Expired: its index is no longer inside the window. Remove from the front.

That requires a deque rather than a stack. Store indices, not only values, because window membership depends on age. Maintain values in decreasing order from front to back. The front is then the current maximum.

Trace the Canonical Sliding Window

Use [1, 3, -1, -3, 5, 3, 6, 7] with k = 3. For each index, perform operations in a fixed order: remove expired front indices, remove dominated back indices, append the new index, then emit the front once the first full window exists. Keep a table with columns for index, value, expired removals, dominated removals, deque and emitted maximum.

The trace should show why the deque never needs every window element. It stores only values that still have a plausible future as maximum.

Advanced: Recognise Windowed Dynamic Programming

Some recurrences contain a hidden sliding maximum, for example a state that needs max(dp[j]) over a forward-moving bounded interval of earlier indices. Recomputing that maximum can turn an O(n) state progression into O(nk). A monotonic deque can sometimes maintain the needed extremum in amortized O(1) per state, restoring O(n) total time.

The professional recognition procedure is mechanical: write the recurrence, identify the candidate interval, check whether the interval endpoints move monotonically, and prove that the dominance rule is valid for the quantity being maximised or minimised. If any of those conditions fail, the pattern may not apply.

Stack, Deque, Heap or Tree?

Common Failure States

• Copying a pop comparison without deciding what equality means.
• Storing values in a sliding-window deque and losing the information needed for expiry.
• Thinking monotonic means the original input must be sorted.
• Calling the nested loop O(n²) without counting lifetime pushes and pops.
• Removing a candidate without proving it can never answer a future query.
• Using the pattern for arbitrary ranges whose boundaries jump backward.

Practice Ladder: Beginner to Professional

• Beginner: brute-force next-greater element and mark repeated comparisons.
• Foundation: trace a monotonic stack with fixed equality rules.
• Intermediate: solve previous/next smaller and histogram-width problems.
• Upper intermediate: derive sliding-window maximum using an index deque.
• Advanced: prove O(n) using aggregate amortized analysis.
• Professional: recognise a bounded-window DP recurrence, justify candidate dominance, benchmark against heap and naive baselines, and test duplicates and extreme window sizes.

Testing Checklist

• All equal values.
• Strictly increasing input.
• Strictly decreasing input.
• Window size 1.
• Window size equal to n.
• Duplicate maxima at different ages.
• Random arrays cross-checked against a slow reference implementation.

Evidence and Learning Design

The amortized argument follows the same aggregate principle developed in the site’s amortized-analysis article: every index enters once and leaves at most once. Sliding-window-max algorithms based on a monotonic candidate structure also appear in research on online signal monitoring, while modern algorithm curricula commonly use the deque formulation as the canonical linear solution. For learning design, code-tracing tutoring research, PRIMM and adaptive Parsons problems support a progression from prediction and tracing toward modification and independent construction.

Final Check

You understand monotonic stack and deque algorithms when you can state exactly why a candidate is discarded, prove that discarded information will never be needed again, explain the linear total operation count, and recognise when window expiry requires a deque rather than a stack.