Monotonic Stacks and Deques: Linear-Time Range Patterns

Many array problems appear to require comparing every position with a long range around it. For each temperature, find the next warmer day. For each histogram bar, find how far its height can extend. For every fixed-size window, report the maximum. For each element, count the subarrays in which it is the minimum. A direct scan from every position is quadratic because it repeatedly revisits candidates that have already been proven useless.

Monotonic stacks and deques make those proofs operational. They retain unresolved indices in value order and discard an index at the moment a newer index dominates it for every future query. Each index enters once and leaves once, yielding linear total work even though one iteration may pop many entries.

The important skill is not recognizing a template. It is writing the invariant: what each retained index is waiting for, why a popped index can never matter again, and how equal values divide ownership. From that invariant, next-greater queries, histogram areas, sliding extrema, and subarray contributions become variations of one elimination argument rather than unrelated tricks.

Maintain Candidates, Not Just Sorted Values #

A monotonic structure stores indices, not only values. An index carries position, expiration, span, and tie-breaking information. Values determine order; indices determine which answer is being resolved.

A monotonic stack usually handles nearest-boundary questions. Its indices follow array order because they are pushed while scanning, while their values are monotone from bottom to top. When a new value violates that order, popping resolves one or more earlier indices.

A monotonic deque handles a moving window. It adds new indices at the back, removes dominated indices from the back, and expires old indices from the front. The front is then the best surviving candidate for the current window.

The shared amortized proof is short. If there are $n$ indices, each is pushed once. Once popped, it never returns. Across the complete scan there are at most $n$ pushes and $n$ pops, so total structural work is $O(n)$ even if a single update performs $O(n)$ pops. This is aggregate analysis, not a claim that every iteration is constant time.

Three choices define the algorithm:

Do not choose these from the words “greater” or “minimum” alone. State what remains unresolved. For next greater to the right, a decreasing stack contains earlier indices still waiting for a strictly greater value. For a sliding maximum, a decreasing deque contains unexpired indices that could still be maximal in some current or future window.

Resolve Next-Greater Boundaries #

Given temperatures [73, 74, 75, 71, 69, 72, 76, 73], find how many positions each day waits for a strictly warmer value. Scan left to right with a stack of unresolved indices whose temperatures are non-increasing from bottom to top.

At index 0, push 73. At index 1, 74 > 73, so pop index 0 and record distance 1. Push index 1. Index 2 similarly resolves index 1. Values 71 and 69 are pushed under 75. When 72 arrives, it pops 69 and 71, recording distances 1 and 2, but it cannot pop 75. Finally 76 resolves 72 and 75. The trailing 73 remains unresolved and receives zero.

export function waitsForStrictlyGreater(values: readonly number[]): number[] {
  const distances = Array<number>(values.length).fill(0);
  const unresolved: number[] = [];

  for (let index = 0; index < values.length; index += 1) {
    while (
      unresolved.length > 0 &&
      values[index]! > values[unresolved[unresolved.length - 1]!]!
    ) {
      const previous = unresolved.pop()!;
      distances[previous] = index - previous;
    }
    unresolved.push(index);
  }

  return distances;
}

Why is the first greater value correct? Every position between previous and the current index failed to pop previous, so none was strictly greater. The current value is greater and is therefore the nearest qualifying boundary. Once answered, previous cannot help any future query because its own result is final.

Equal values expose the comparison contract. With strict greater, an equal current value does not resolve an earlier index, so the stack is non-increasing and duplicates may coexist. For next greater-or-equal, use >=; the earlier equal index is resolved immediately. Changing only prose while leaving the comparator unchanged answers a different problem.

Scanning right to left offers another form: pop candidates that cannot qualify, then the stack top is the nearest surviving boundary. Both approaches are valid, but their invariants differ. The left-to-right form resolves old indices when evidence arrives; the right-to-left form selects an answer for the current index from already-seen future candidates.

Derive the Largest Histogram Rectangle #

For histogram heights [2, 1, 5, 6, 2, 3], every rectangle is limited by its shortest bar. Treat each bar as the limiting height and ask how far it extends before a smaller bar appears on each side. A monotonic increasing stack can discover the right boundary when a shorter height arrives while retaining the left boundary implicitly.

Store indices with nondecreasing heights. When current height is smaller than the stack-top height, pop the top. The current index is the first smaller boundary on the right. After popping, the new stack top is the nearest smaller boundary on the left; if the stack is empty, the rectangle reaches the beginning. Thus

At height 2 in index 4, bar 6 at index 3 pops first. Its left smaller boundary is index 2, so its width is $4-2-1=1$ and area is 6. Bar 5 at index 2 then pops. Its left smaller boundary is index 1, so its width is $4-1-1=2$ and area is 10. That is the maximum for this input.

export function largestRectangle(heights: readonly number[]): number {
  const increasing: number[] = [];
  let best = 0;

  for (let right = 0; right <= heights.length; right += 1) {
    const currentHeight = right === heights.length ? 0 : heights[right]!;

    while (
      increasing.length > 0 &&
      currentHeight < heights[increasing[increasing.length - 1]!]!
    ) {
      const height = heights[increasing.pop()!]!;
      const left = increasing.length === 0
        ? -1
        : increasing[increasing.length - 1]!;
      best = Math.max(best, height * (right - left - 1));
    }

    increasing.push(right);
  }

  return best;
}

The virtual zero-height bar at right === heights.length flushes every remaining positive bar. It avoids a duplicated cleanup loop. Inputs must reject negative heights if the domain says heights are nonnegative, and numeric types must hold height * width without overflow.

Duplicates can use either a strict pop as above or a non-strict pop with adjusted ownership. With strict <, equal bars coexist and the earlier one eventually receives the wider span. With <=, the newer equal bar replaces the earlier candidate and inherits future extension. Both can produce the correct maximum if width boundaries are consistent; mixing a comparator from one convention with boundary logic from another causes off-by-one areas.

Keep Sliding-Window Extrema in a Deque #

For each window of size $k$, a heap can report the maximum in $O(n\log k)$ time, but a monotonic deque reaches $O(n)$. The deque stores indices in decreasing value order. Before inserting a new index, remove indices from the back whose values are less than or equal to the new value. They are dominated: the new value is at least as large and expires later, so they can never again become a window maximum.

Before reading the answer, remove the front if it lies before the current window. The front then holds the largest unexpired value.

export function slidingMaximum(values: readonly number[], windowSize: number): number[] {
  if (!Number.isInteger(windowSize) || windowSize < 1 || windowSize > values.length) {
    throw new RangeError('windowSize must be between 1 and values.length');
  }

  const deque: number[] = [];
  let head = 0;
  const maxima: number[] = [];

  for (let index = 0; index < values.length; index += 1) {
    while (head < deque.length && deque[head]! <= index - windowSize) head += 1;

    while (
      head < deque.length &&
      values[deque[deque.length - 1]!]! <= values[index]!
    ) {
      deque.pop();
    }

    deque.push(index);
    if (index >= windowSize - 1) maxima.push(values[deque[head]!]!);

    if (head > 1024 && head * 2 > deque.length) {
      deque.splice(0, head);
      head = 0;
    }
  }

  return maxima;
}

For values [1, 3, -1, -3, 5, 3, 6, 7] and $k=3$, the outputs are [3, 3, 5, 5, 6, 7]. When 5 arrives, it removes -3 and the older -1 from the back; both are smaller and will expire earlier. The prior 3 has already expired from the front. 5 is therefore the only candidate needed for that window.

The head offset avoids an $O(n)$ array shift on every expiration. A language with a true deque should use it directly. The occasional compaction preserves linear total copying because it occurs only after a substantial dead prefix accumulates.

Using <= at the back keeps the newest equal maximum, minimizing retained duplicates. Using < keeps equal indices and still returns correct values if expiration is correct. If the result also needs the earliest index attaining the maximum, the tie rule becomes part of the output contract rather than a memory preference.

Count Subarrays by Contribution #

Some problems ask for an aggregate over all subarrays, such as the sum of every subarray minimum. Enumerating $O(n^2)$ subarrays is unnecessary. Reverse the counting: for each index, count how many subarrays choose that element as their representative minimum, then multiply by its value.

Let $L_i$ be the distance from index $i$ to a boundary on the left and $R_i$ the distance to a boundary on the right. If index $i$ owns every subarray whose start has $L_i$ choices and end has $R_i$ choices, its contribution is

For [3, 1, 2, 4], value 1 at index 1 can extend left across 3 and right across 2, 4. It has two start choices and three end choices, so it is the minimum of six subarrays and contributes 6. Value 3 owns only [3], contributing 3. Value 2 owns [2] and [2, 4], contributing 4. Value 4 owns [4], contributing 4. The total sum is 17.

Duplicates require asymmetric boundaries so every subarray has exactly one owner. One valid convention for minima is:

• On the left, stop at the previous value strictly less than the current value.
• On the right, stop at the next value less than or equal to the current value.

For [2, 2], this convention lets the left 2 own [2] at index 0, while the right 2 owns [2] at index 1 and [2, 2]. If both boundaries were strict, both equal positions could claim the shared subarray. If both were non-strict, neither might claim it under the corresponding span formulas.

The exact comparator direction can be reversed: previous less-or-equal with next strictly less assigns ties to the other side. Correctness needs one strict and one non-strict boundary, plus consistent distance calculations. For maxima, reverse the inequalities. For modular output, reduce after multiplication using a numeric type that cannot overflow before the modulus is applied.

Recognize Failure Modes and Alternative Structures #

Monotonic structures work when future usefulness follows a dominance order. In a sliding maximum, a newer value at least as large dominates an older one because it is better now and expires later. If updates can change arbitrary old values, that dominance proof fails; use a segment tree, balanced tree, indexed heap, or another dynamic structure.

Common implementation failures follow directly from an unstated invariant:

• Storing values when answers require distances or expiration indices.
• Expiring after emitting the window answer, allowing a stale maximum into one extra window.
• Using shift() on a flat array and accidentally turning a linear deque algorithm quadratic.
• Forgetting to flush a stack whose answers are resolved only by a later boundary.
• Changing < to <= without revisiting duplicate ownership.
• Multiplying large values and spans in a type that silently overflows.
• Applying the pattern to a circular array without defining the bounded second pass.

A stack is not always the clearest implementation. If nearest boundaries for many later queries are needed, compute and retain boundary arrays. If fixed-window extrema must support online deletion by arbitrary identifier, a multiset may better match the operations. If only one pass and one aggregate are needed, a stack can often accumulate spans directly and reduce memory, but that compressed form needs an equally explicit invariant.

Complexity claims also need the right unit. A monotonic stack uses $O(n)$ worst-case memory when all values are already monotone in the retained direction. The deque uses $O(k)$ live candidates for a window of size $k$, excluding dead storage in a poor container implementation. Linear time does not imply constant space.

Verify Invariants with Brute-Force Oracles #

Tiny brute-force implementations are ideal test oracles. For next greater, scan right from each index. For histogram area, enumerate every interval and track its minimum height. For sliding maxima, compute Math.max over each copied window. For contribution sums, enumerate every subarray. Compare the linear algorithm against the oracle across generated arrays small enough that quadratic or cubic work is cheap.

Bias generated tests toward structures that stress comparisons: all equal, strictly increasing, strictly decreasing, alternating high and low, repeated plateaus, negative values where allowed, one element, and windows of size 1 or $n$. Shrinking a failing generated case often reveals a two- or three-element duplicate boundary error.

Assert the invariant during test builds. After each update, stack indices must increase and their referenced values must have the documented monotonic relation. Deque indices from head onward must increase, remain inside the active window, and have decreasing values. Count pushes and pops to confirm each index is removed at most once; this catches accidental reinsertion that can invalidate the amortized proof.

Metamorphic properties add coverage. Adding a constant to every temperature does not change next-greater distances. Scaling nonnegative histogram heights by a positive factor scales the best area by that factor. Increasing the window size cannot make a window’s maximum smaller when comparing nested windows with the same right edge. Reversing an array and swapping previous/next boundary logic should produce mirrored relationships.

The practical derivation is always the same. Name the unresolved candidates. Define the value order. Prove why a newly arrived index permanently dominates each popped index. Decide who owns equal values. Then prove each index enters and leaves only once. With those statements in place, the code is short because the reasoning has already removed every candidate that no future answer could need.