229: Monotonic Stacks and Monotonic Queues

Learning outcomes

By the end of this lesson, you can:

explain and apply a monotonic stack in a realistic implementation;
explain and apply the “each element is pushed once” amortized argument in a realistic implementation;
explain and apply next-greater and next-smaller searches in a realistic implementation;
explain and apply histogram-area reasoning in a realistic implementation;
explain and apply a monotonic deque in a realistic implementation.

Prerequisites and retrieval

This lesson assumes the 01–06 foundation and the preceding lessons in this module. Before you start, retrieve one concrete example from an earlier project where you had to keep only the candidates that could still affect a later result. It might have been a nearest match, a running extreme, or a sliding-window calculation. The exact example is less important than the reasoning: which candidates could safely be discarded, and what evidence justified discarding them?

The goal here is not to memorize a stack or deque template. You should be able to make a defensible choice in an interview-sized problem and in a production data-processing problem. That means starting with constraints and an invariant, then selecting the data structure that makes those constraints visible and provable.

Terminology

Monotonic stack: A stack whose stored indices or values are kept in increasing or decreasing order. A new value can force the removal of entries that no longer have a possible future answer.
Each element pushed once: The amortized reason these algorithms are often linear. Each element is inserted once and removed once, even if one iteration removes many elements.
Next greater/smaller: A family of searches for the first later or earlier value that is greater or smaller than the current value. The stack direction and comparison strictness depend on whether equal values count as a match.
Histogram area: A largest-rectangle calculation in which an increasing stack finds the interval over which a popped bar is the limiting height. A sentinel bar is a convenient way to flush entries left in the stack.
Monotonic deque: For a sliding-window maximum, expired indices leave from the front and smaller, dominated values leave from the back. The largest still-valid value therefore remains at the front.
Proof by domination: The argument that a discarded candidate can never become optimal before the newer candidate that dominates it expires. This is what makes permanent removal safe rather than merely convenient.

Mental model

Many of these problems look quadratic because every new value seems to need comparisons with many earlier values. The useful shift is to stop treating every earlier value as equally valuable. Keep only candidates that can still matter to a future answer, and remove a candidate as soon as the current input proves that it is no longer useful.

That is the role of a monotonic stack or deque. The structure is not just an optimization wrapped around a loop; its ordering is an invariant. The invariant tells you what the stored entries mean, when an entry may be removed, and what the front or top represents after each input is processed.

Treat Monotonic Stacks and Monotonic Queues as a design problem with observable inputs, outputs, invariants, and failure modes. A strong implementation makes assumptions visible, narrows uncertainty at boundaries, and leaves enough evidence—tests, types, constraints, metrics, or diagrams—to explain why the design is safe.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from a requirement directly to a library call or a familiar code template. First state what must remain true. Then choose the mechanism that enforces it. For example, if the answer depends on position, store indices rather than only values; if values can be equal, decide explicitly whether “greater” means > or >=.

Deep dive

1. Monotonic stack

The recurring problem is that a value may have no answer yet, but later input can resolve it. A monotonic stack stores the unresolved candidates in an order that makes those resolutions cheap. Depending on the question, the stack may be increasing or decreasing, and it may hold values or indices.

When a new value violates the maintained order, pop entries while the comparison says their next greater or smaller answer has arrived. The popped entries are not being discarded arbitrarily: the current value is the first qualifying value found for them, assuming the scan direction and comparison rule match the requirement.

Decision rule: Use a monotonic stack deliberately when its contract or invariant is easier to prove with it. If it only reduces typing while hiding an assumption about duplicates, scan direction, or boundary behavior, use a more explicit design.

2. Each element pushed once

The phrase “each element is pushed once” does not mean every loop iteration performs constant work. One iteration can pop many entries. The linear bound comes from amortization: an entry can be pushed into the stack once and removed from it once. Across the entire scan, all of those removals add up to at most the number of pushes.

This distinction matters when reviewing complexity. Looking at the inner while loop and calling the algorithm quadratic is too pessimistic; multiplying the maximum number of pops by the number of iterations is not how the work is distributed. The total number of stack operations is still O(n), with O(n) additional storage in the worst case.

Decision rule: Use the “each element is pushed once” argument when it makes the runtime and invariant easier to prove. If the implementation has extra work inside the pop loop, account for that work separately rather than assuming the amortized argument covers it.

3. Next greater/smaller

Next-greater and next-smaller problems ask for the nearest qualifying value, usually to the right of each position, although the same reasoning can be applied in the other direction. Choose the stack direction from the comparison you need. A decreasing stack is a common starting point for resolving next-greater values; an increasing stack is common for next-smaller values.

The subtle part is equality. “Next greater” normally means strictly greater, so equal values do not resolve one another. A problem that says “greater than or equal to” needs a different pop condition. Store indices when the result includes a distance or position, not just the matching value. Unresolved entries left after the scan receive the problem’s explicit “not found” result, such as -1 or a sentinel distance.

Decision rule: Use next-greater or next-smaller reasoning deliberately when the ordering and comparison strictness are part of a clear invariant. If equal values, circular input, or multiple valid interpretations are not specified, clarify the contract before implementing.

4. Histogram area

For the largest rectangle in a histogram, the question is not simply which bar is tallest. A bar can be the limiting height for a range of adjacent bars. An increasing stack keeps candidate bars whose left boundary has not yet been determined. When a shorter bar arrives, it proves that each taller popped bar cannot extend through the current position.

At the point a bar is popped, its height is known. The current index supplies the exclusive right boundary, and the new stack top supplies the nearest smaller bar on the left. Those two boundaries determine the width of the largest rectangle for which the popped bar is the limiting height. A sentinel bar of height zero at the end forces the same calculation for entries that would otherwise remain on the stack.

Decision rule: Use histogram-area reasoning deliberately when the invariant identifies a bar’s maximal contiguous interval. Be explicit about whether indices refer to bars or sentinels, whether an empty stack means the interval starts at zero, and how equal-height bars are handled.

5. Monotonic deque

Sliding-window maximum has two separate expiration problems. An index can become too old and must leave from the front. A newer index with an equal or larger value can make an older smaller index permanently irrelevant, so those dominated entries leave from the back.

The deque stores indices, not just values. That lets the algorithm remove expired entries by comparing their positions with the current window's left boundary. After expired entries and dominated entries are removed, the front is the maximum among the current window. Each index enters once and leaves once, so the scan is O(n) and the deque uses O(k) space for a window of size k.

Decision rule: Use a monotonic deque deliberately when the answer is an extreme over a moving range and both validity by position and domination by value matter. If the window is not contiguous, or if updates and queries have different requirements, another structure may make the contract clearer.

6. Proof by domination

Suppose an older candidate and a newer candidate are both in consideration, and the newer candidate is at least as good for the query. The newer candidate also expires later because it entered the window later. Until the newer candidate expires, the older one cannot win; after that point, the older one has already expired or is no longer needed under the invariant. The older candidate is therefore dominated and can be removed permanently.

This is the proof behind popping from a monotonic stack and deque. It is also the part that should be explained in a code review. “The template says to pop” is not a correctness argument. State why the removed entry cannot become the answer later, especially when equal values and expiration boundaries are involved.

Decision rule: Use proof by domination deliberately when you can name both the ordering relationship and the expiration relationship. If either condition is missing, do not discard a candidate without a separate proof.

Worked example

Start with the requirement, not with the data structure. For an interview-sized problem or a production data-processing job, write the requirement in one sentence, list the input and output contracts, and identify which concept owns each failure mode. Then ask whether a candidate can be permanently dominated, whether position matters, and what the invariant should be after each input is processed.

The example below is intentionally a simple baseline scan. It shows the shape of a contract and an invariant comment, but it is not a monotonic-stack solution. That distinction matters: a running maximum is enough when the requirement is only the maximum value, whereas next-greater, histogram, and sliding-window requirements need additional positional reasoning.

function solve(values: readonly number[]): number {
  let answer = 0;
  // State the invariant before choosing the data structure.
  for (const value of values) {
    answer = Math.max(answer, value);
  }
  return answer;
}

There is already a contract question here: returning 0 for an empty input is only correct if the domain defines zero as the identity or default result. If negative values are valid and the intended result is the maximum element, this implementation is wrong because the initial value changes the answer. A production implementation should define whether the input may be empty and represent “no result” explicitly when necessary.

Walk the example with at least four cases: the normal path; an empty or missing value; a duplicate, retry, or concurrent path where that situation is relevant; and a dependency failure. For each case, state which layer detects the problem and what the caller observes. In the monotonic problems from this lesson, add duplicates and boundary positions to that list: equal values can change the pop condition, and the first or last index can change the computed width or expiration result.

The separation of concerns remains important. Parsing and validation belong at the boundary; domain rules belong in the domain or service layer; persistence rules belong in the database or repository; presentation rules belong in the client. Mixing these concerns can make a happy-path demo look shorter, but it makes algorithmic edge cases and operational failures harder to reason about.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high cardinality. For monotonic structures, also ask whether the input can exceed memory, whether the window size is bounded, whether integer arithmetic can overflow in an area calculation, and whether an invalid ordering or missing value has a defined result.

Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after you can identify the bottleneck or risk with evidence. A linear algorithm is not automatically safe if its O(n) storage is unbounded or if the result is computed with a numeric type that cannot represent the required range.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and network input is untrusted. The stack or deque may be correct while the surrounding boundary still accepts malformed data or reports an ambiguous failure.

Guided lab

Solve daily temperatures or next-greater-element, largest rectangle in a histogram, and sliding-window maximum. For each problem, write the invariant before the loop and explain why every removed element can never matter again. Include the comparison rule for equal values and the value returned for unresolved entries.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

For the lab's edge cases, include an empty input, a single value, already sorted input, reverse-sorted input, repeated values, and values that leave candidates unresolved until the final sentinel or end-of-input step. These cases expose incorrect comparison strictness and forgotten cleanup more reliably than a random happy-path example.

Edge cases and failure modes

Monotonic stack: Test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes. Verify the stack's ordering after every meaningful operation when debugging.
Each element pushed once: Test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes. Confirm that each index is not reinserted after removal and account for work performed inside the pop loop.
Next greater/smaller: Test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes. Check strict versus non-strict comparisons and the representation of “no next value.”
Histogram area: Test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes. Check equal heights, zero-height bars, a monotonic sequence, the empty-stack left boundary, the final flush, and width or numeric overflow.
Monotonic deque: Test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes. Check window size one, a window equal to the input, expired front indices, dominated back indices, and equal values.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong. A running maximum, for example, does not answer a next-greater query or preserve enough information for a histogram width.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or temporary any values.
Testing only the happy path and discovering the contract only after integration.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees.
Choosing > versus >= by habit instead of from the definition of the problem.
Storing values when the answer requires indices, or forgetting to remove expired indices before reading the deque front.
Forgetting to flush a stack at the end of a histogram or next-greater scan, leaving valid candidates without an answer.

For debugging, reproduce the smallest failing case, inspect the actual value, index, and computed boundary, and trace the first point where the invariant becomes false. In a histogram, log the popped height and both exclusive boundaries. In a sliding window, log the current left boundary and the indices at both deque ends. Then fix the owning layer rather than adding a downstream patch.

Interview questions

What problem does a monotonic stack solve, and what trade-off or failure mode would make you choose a different approach?
What problem does the “each element is pushed once” argument solve, and what trade-off or failure mode would make you choose a different approach?
What problem does next-greater or next-smaller reasoning solve, and what trade-off or failure mode would make you choose a different approach?
What problem does histogram-area reasoning solve, and what trade-off or failure mode would make you choose a different approach?
What problem does a monotonic deque solve, and what trade-off or failure mode would make you choose a different approach?

Checkpoint

Without notes, explain Monotonic Stacks and Monotonic Queues to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code. As a useful check, explain why the removed candidate is permanently irrelevant rather than merely irrelevant for the current iteration.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost, including the amortized “push once, pop once” argument.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.