Stacks and monotonic stacks

A stack answers one question: what is the most recent thing that is still unresolved? Every use of it, from bracket matching to the largest rectangle in a histogram, is that question wearing a different hat. When a problem's answer depends on the nearest earlier element rather than on all earlier elements, a stack turns a quadratic scan into a single pass.

The plain case: matching brackets

Reading ([)], the closing ) has to be checked against the most recent opener still waiting for its partner. Nothing older matters. That is a stack, and the code is the definition:

PAIRS = {')': '(', ']': '[', '}': '{'}

def balanced(s):
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif not stack or stack.pop() != PAIRS[ch]:
            return False
    return not stack          # anything left never closed

Two failure modes, two lines: a closer with nothing to match (not stack), and openers still on the stack at the end. Candidates who forget the second return True for (((.

Monotonic: the stack keeps an order, and breaking it is the event

Now the harder shape. For each element, find the first larger value to its right. The brute force scans forward from every index: at n = 100,000 that is about n²/2 = 5 × 10⁹ comparisons. Assume a conservative 10⁷ Python-level operations per second and that is around 500 seconds. The monotonic version does 2n = 200,000 stack operations — about 0.02 s on the same assumption.

The waste, in the language of the solving loop, is that the forward scan re-examines elements that an earlier scan already ruled out. Take 7 sitting to your left. Anything smaller than 7 that sat to 7's left was already answered by 7 itself when 7 arrived, so it is not waiting any more. The elements still unresolved by the time you arrive are therefore exactly a decreasing run in index order — 7 nearest you, larger values further back — and if you are 9, you resolve every one of them below 9 with a single pop each, then join the run yourself.

So keep the waiting elements on a stack, in order. Reading from the top down, the values increase: the top is the smallest thing still waiting, the bottom the largest. A new element that is bigger than the top breaks that order, and breaking it is the whole event — every element it pops has just found its answer.

A monotonic stack at three moments: three indices waiting, one larger element popping all of them, and the leftovers that never find an answer100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

def next_greater(nums):
    ans = [-1] * len(nums)
    stack = []                       # indices; values increase from the top down
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            ans[stack.pop()] = x     # x is the first larger value to its right
        stack.append(i)
    return ans                       # indices still on the stack have none

There is a while inside a for, which looks quadratic and is not. Each index is pushed exactly once and popped at most once, so the inner loop runs at most n times in total across the whole scan — 2n stack operations, O(n). Say that sentence out loud when you write this; it is the thing being graded, and it is the same style of argument as the amortised cost in queues and amortised cost.

The histogram rectangle

Same machine, one more step of bookkeeping. For each bar in a histogram, the widest rectangle at that bar's height runs from the first shorter bar on its left to the first shorter bar on its right. Both boundaries are "nearest smaller element" queries, and a bar is resolved the moment something shorter arrives.

def largest_rectangle(heights):
    stack = []                                  # indices; heights increase upward
    best = 0
    for i, h in enumerate(heights + [0]):       # 0 is a sentinel that flushes
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            left = stack[-1] + 1 if stack else 0
            best = max(best, height * (i - left))
        stack.append(i)
    return best

The pop gives the height. The right boundary is i, the bar that ended it. The left boundary is whatever is now below on the stack, plus one — because everything between them was taller, which is exactly what being on the stack means. The trailing 0 is there so bars that never meet a shorter neighbour are still popped and measured; without it, a strictly increasing histogram returns 0.

The recipe

Four decisions cover every problem in this family.

Store indices, not values. You can always read the value with one lookup, but you cannot recover a position from a value, and almost every question in this family wants a width or a distance — i - stack[-1].

Decide what popping means, in one sentence. "The popped index has just found the first element larger than it." If you cannot say that sentence, the loop condition is guesswork.

Pick the comparison from the question. Pop while the top is smaller and you get next greater; pop while the top is larger and you get next smaller. Whether to use < or <= is decided by what should happen on ties — with duplicates, <= resolves the earlier equal element at the later one and < leaves it for something strictly bigger.

Plan for the leftovers. Whatever is on the stack when the scan ends never found its answer. Either pre-fill the result (-1 above), or push a sentinel that pops everything (the 0 in the histogram).

Scanning right to left with the mirror-image invariant answers the same questions about the left side; either direction works, and picking the one that makes the answer fall out at pop time saves a second pass.

In an interview

The tell is in the problem statement: "nearest", "next", "previous", "first element to the right that…", "span", "how far until". All of them mean the answer depends on one neighbour, not on a whole prefix, and a stack finds that neighbour for free.

Narrate the invariant before the code — "the stack holds indices whose values increase from the top down, so the top is the nearest unresolved candidate" — then the complexity argument, then write. Three sentences and the interviewer knows you have not memorised this.

The mistake that loses points is writing the loop correctly and then answering "O(n²)?" when asked for the complexity, or asserting O(n) with no reason. The nested while is exactly what an interviewer probes; push-once, pop-once is the answer, and it costs one sentence.

Check yourself

Your stack holds indices with values increasing from the top down, and you pop while the top's value is smaller than the current element. Which question are you answering, and for which element?

Next greater element, and you are answering it for the popped index, not the current one. The current element is the answer being handed out; it gets its own answer later, when something bigger pops it.

A colleague says the monotonic-stack loop is O(n²) because of the while inside the for. Give the counter-argument in one sentence, with the count.

Every index is pushed once and popped at most once, so all executions of the inner loop together account for at most n pops — 2n operations for the whole scan, not n per element.

On the histogram, what breaks if you drop the trailing sentinel?

Any bar never followed by a shorter one stays on the stack and is never measured. On strictly increasing heights nothing is ever popped, and the function returns 0 instead of the largest rectangle.