“Use a monotonic stack” is not an explanation. The useful skill is recognizing why unresolved candidates can be discarded and proving that each element is processed a constant number of times.

Consider the next-greater-element problem: for every position, find the first value to its right that is larger.

Formally, for an array a[0..n-1]:

NGE(i) = min { j | j > i and a[j] > a[i] }

If that set is empty, return a sentinel such as n or -1. Writing the relation explicitly matters: “greater” and “greater or equal” produce different stack invariants when duplicates exist.

Derive it from the failed brute force

The direct solution scans right from every index. It is easy to verify and costs O(n²) in a decreasing array because no scan finds an answer early.

What work is repeated? Multiple indices are waiting for a future value large enough to resolve them. We can keep those unresolved indices together.

When reading values[i], compare it with the most recent unresolved index:

  • if the current value is larger, it is the first larger value for that index;
  • pop the resolved index and keep comparing;
  • push the current index because it now waits for its own answer.
def next_greater(values):
    answer = [-1] * len(values)
    stack = []  # indices; values are monotonically decreasing

    for i, value in enumerate(values):
        while stack and values[stack[-1]] < value:
            unresolved = stack.pop()
            answer[unresolved] = value
        stack.append(i)

    return answer

State the invariant

After processing index i, the stack contains only indices whose next greater value has not appeared. Their values are in decreasing order from bottom to top.

Why can we pop safely? The current value is greater, and every earlier processed value failed to resolve that index. Therefore the current position is the first valid answer.

Why keep indices instead of values? Many variations need distances, spans, boundaries, or duplicate handling. The index preserves all of that information.

Correctness, not intuition

Suppose index j is popped when the scan reaches i because a[i] > a[j].

  1. i is a valid greater element by the loop condition.
  2. If some k with j < k < i had a[k] > a[j], then j would have been popped when the scan visited k.
  3. Because j survived until i, no earlier position to its right was greater.

Therefore i is the first greater position, not merely some greater position. At termination, every index still on the stack has no greater value to its right because the scan examined the complete suffix.

The complexity proof is accounting

The nested while loop looks quadratic, but an index is pushed once and popped at most once. Across the entire input there are at most n pushes and n pops, so total stack work is O(n).

This is amortized analysis: one iteration may pop many entries, but those entries can never be popped again.

More precisely, there are n pushes, at most n successful pop-loop iterations, and at most one final failed comparison per outer iteration. The total is Θ(n) time and O(n) auxiliary space. This does not mean every input step is worst-case O(1); one step can pop the entire stack.

Duplicates change the contract

For “next strictly greater,” pop while <. For “next greater or equal,” pop while <=. That one character decides which duplicate remains as a boundary.

Always write the comparison from the problem’s exact language. Many histogram and range-contribution bugs come from copying a strict comparison into a non-strict boundary problem.

For a left-to-right scan that assigns the current index as the next boundary of every popped item:

  • next strictly greater: pop while top < current; equal values remain;
  • next greater-or-equal: pop while top <= current; equal values pop;
  • next strictly smaller: pop while top > current; equal values remain;
  • next smaller-or-equal: pop while top >= current; equal values pop.

Reverse the traversal or change whether the answer comes from a pop versus the surviving top, and the interpretation changes. A memorized comparison table is still weaker than writing the target relation first.

Duplicate ownership in subarray minimums

The difficult version of this pattern is not next-greater. It is assigning each subarray to exactly one occurrence of its minimum.

For index i, choose:

  • L(i): previous index with a value strictly less than a[i];
  • R(i): next index with a value less than or equal to a[i].

Then a[i] is the selected minimum for:

(i - L(i)) × (R(i) - i)

subarrays, contributing:

a[i] × (i - L(i)) × (R(i) - i)

Why asymmetric comparisons? Consider [2, 2]. With “previous strictly less / next less-or-equal,” the first 2 owns [0,0]; the second owns [1,1] and [0,1]. Every subarray has exactly one owner. Using strict comparison on both sides double-counts the two-element range; using non-strict on both sides leaves it unowned.

The mirror convention—previous less-or-equal and next strictly less—is also valid. Mixing conventions halfway through an implementation is not.

Recognize the family

The same unresolved-candidate idea appears in:

  • Daily Temperatures: store indices and output the distance to the resolving day.
  • Stock Span: pop smaller previous prices and aggregate the dominated span.
  • Largest Rectangle in Histogram: find the first smaller boundary on both sides.
  • Sum of Subarray Minimums: count how many ranges select each value as their minimum.
  • Remove K Digits: pop previous digits while doing so creates a smaller lexicographic result.

The direction and monotonic order depend on which boundary is needed. “Next greater to the right” and “previous smaller to the left” are different traversals with the same core invariant.

Know when not to use it

A monotonic stack fits when:

  1. candidates wait for a future or previous boundary;
  2. a new element can permanently dominate some candidates;
  3. dominated candidates will never become useful again.

It does not fit arbitrary range queries where candidates can become relevant again. Segment trees, sparse tables, heaps, or offline sorting may be the right model there.

A better interview explanation

Explain the algorithm in this order:

  1. identify the repeated scan in the brute-force solution;
  2. define what each stack entry is waiting for;
  3. state the monotonic invariant;
  4. justify why a pop is permanent;
  5. prove push-once, pop-once complexity;
  6. test increasing, decreasing, duplicate, and single-element inputs.

That explanation transfers to new problems. Memorizing a dozen stack-shaped solutions does not.

Verify the implementation, not the pattern name

For small arrays, compare the stack algorithm with a brute-force oracle. Exhaustively enumerate lengths 0..7 over values {0,1,2}; the small alphabet deliberately creates duplicate plateaus.

Include these families:

  • empty and singleton arrays;
  • all equal;
  • strictly increasing and decreasing;
  • alternating high/low values;
  • long plateaus with a boundary at either end.

For contribution problems, add a structural assertion before checking the weighted sum:

Σ (i - L(i)) × (R(i) - i) = n(n + 1) / 2

The right side is the number of contiguous subarrays. If the ownership count differs, the duplicate-boundary logic is wrong regardless of the values.

References