Stack pattern: template and problems

When it applies

A stack fits when each element's answer depends on the nearest element to one side that satisfies some comparison: the next larger value, the previous smaller one, the bracket that closes this one. Elements whose answer is still unknown sit on the stack. When a new element arrives, it settles every waiting element it beats, and those leave for good.

The stack stays in sorted order (a monotonic stack), because anything the new element beats is removed before the new element goes on. Each index is pushed once and popped at most once, so the loop is O(n) even though it contains a while.

Signals: "next greater", "previous smaller", "days until", "span", "largest rectangle", "valid brackets", "evaluate an expression", "undo". If you catch yourself scanning left or right from every index looking for the first bigger value, you want a stack.

The template

Write this from memory. Every problem in this section is a specialisation of it, and most bugs come from deviating without a reason.

stack = []                    # indices still waiting
for i, x in enumerate(a):
    while stack and a[stack[-1]] < x:
        j = stack.pop()           # x settles j
        answer[j] = i             # first larger value after j
    stack.append(i)               # i waits for its own answer

std::vector<int> stack;            // indices still waiting
for (int i = 0; i < (int)a.size(); ++i) {
    while (!stack.empty() && a[stack.back()] < a[i]) {
        answer[stack.back()] = i;       // first larger value after it
        stack.pop_back();
    }
    stack.push_back(i);
}

int[] stack = new int[a.length];         // indices; top is stack[top - 1]
int top = 0;
for (int i = 0; i < a.length; i++) {
    while (top > 0 && a[stack[top - 1]] < a[i])
        answer[stack[--top]] = i;       // first larger value after it
    stack[top++] = i;
}

const stack = [];                  // indices still waiting
for (let i = 0; i < a.length; i++) {
  while (stack.length && a[stack[stack.length - 1]] < a[i]) {
    const j = stack.pop();
    answer[j] = i;                     // first larger value after j
  }
  stack.push(i);
}

let mut stack: Vec<usize> = Vec::new();   // indices still waiting
for i in 0..a.len() {
    while let Some(&j) = stack.last() {
        if a[j] >= a[i] { break; }
        answer[j] = i;                  // first larger value after j
        stack.pop();
    }
    stack.push(i);
}

-- The stack is a list, top at the head. x pops what it beats.
step (stack, settled) (i, x) =
  let (beaten, rest) = span (\j -> arr ! j < x) stack
  in (i : rest, [(j, i) | j <- beaten] ++ settled)

Problems

Easy10 min

Or sit a timed interview: a fixed window, limited submissions, and a report at the end.

Stack

When it applies

The template

Problems

Balanced brackets

Days until a warmer day

Largest rectangle in a bar chart