Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Stack and Monotonic Stack

The stack pattern solves problems where the most recent unfinished item is handled first: matching pairs, undoing, and finding the next greater element.

The stack pattern solves problems in which the item that must be dealt with next is always the most recent one still unfinished. Items wait on a stack until something arrives that settles them.

The idea

Think of opening brackets while reading code. Each ( or { is a promise that a matching closer will arrive later. When a closer does arrive, it must match the most recent opener still waiting, not the first one. Last opened, first closed: that is exactly the order a stack hands things back in.

Many problems share this shape even when they have nothing to do with brackets. An item arrives and cannot be resolved yet, so it is pushed. A later item resolves it, so it is popped. Whatever is left on the stack at the end was never resolved.

In JavaScript an array is the stack: push adds to the top, pop removes from the top, and stack[stack.length - 1] looks at the top without removing it. All three are O(1).

When to use it

  • Things must be matched in pairs that can nest: brackets, tags, function calls.
  • The newest item can cancel or combine with the one just before it: undo, removing adjacent duplicates, simplifying a path.
  • For each element you need the next greater or next smaller element to its left or right.
  • You need the span over which an element is the smallest or largest, as in histogram and temperature problems.
  • A brute-force solution scans backwards or forwards from every element to find the nearest one with some property.

Form 1: match or cancel the most recent item

Push each item. Before pushing, check whether it settles the item on top.

// Repeatedly delete two equal letters that sit side by side.
function removeAdjacentPairs(text) {
  const stack = [];
  for (const ch of text) {
    if (stack.length > 0 && stack[stack.length - 1] === ch) {
      stack.pop();        // ch cancels the letter on top
    } else {
      stack.push(ch);     // ch waits for a partner
    }
  }
  return stack.join("");
}

For "abbaca": the two bs cancel, which brings the two as together, and they cancel too, leaving "ca". The stack handles that chain reaction without rescanning the string, because after a pop the new top is automatically the letter that is now adjacent.

Form 2: the monotonic stack

A monotonic stack is a stack whose contents are always in sorted order, because anything that would break the order is popped before a new item is pushed. It answers "what is the next greater element?" for every position in one pass.

The stack holds the positions still waiting for their answer. When a new value arrives, it is the answer for every waiting position whose value is smaller, so those are popped and filled in.

// For each number, the next number to its right that is larger, or -1.
function nextGreater(numbers) {
  const result = new Array(numbers.length).fill(-1);
  const waiting = []; // indexes with no answer yet
 
  for (let i = 0; i < numbers.length; i++) {
    while (
      waiting.length > 0 &&
      numbers[waiting[waiting.length - 1]] < numbers[i]
    ) {
      result[waiting.pop()] = numbers[i];
    }
    waiting.push(i);
  }
  return result;
}

For [2, 1, 2, 4, 3]:

i (value) Popped and answered Waiting after (as values)
0 (2) 2
1 (1) 2, 1
2 (2) 1 gets 2 2, 2
3 (4) 2 gets 4, 2 gets 4 4
4 (3) 4, 3

The result is [4, 2, 4, -1, -1]. The two values still waiting at the end have nothing larger to their right.

Why the stack stays in order

The values waiting on the stack never increase from bottom to top. If a larger value arrived above a smaller one, the smaller one would have been popped first. That ordering is what makes the while loop correct: once the top is not smaller than the new value, nothing beneath it is either, so the loop can stop.

The four variations

The same loop covers four questions. Only the comparison and the direction of travel change.

To find Pop while the top is Scan
Next greater element smaller than the new value left to right
Next smaller element larger than the new value left to right
Previous greater element smaller or equal; the answer is the top that remains left to right
Previous smaller element larger or equal; the answer is the top that remains left to right

Store indexes, not values, on the stack. The value is always available through the index, and the index is needed whenever the question is about distance or width.

Complexity

  • Time: O(n). The while inside the for looks like O(n²), but each index is pushed once and popped at most once. However the pops are distributed, there are at most n of them in total.
  • Space: O(n) in the worst case, when nothing is resolved until the end: a string of only opening brackets, or a list of falling values.

Common mistakes

  • Reading the top of an empty stack. Check stack.length > 0 before looking at or popping the top.
  • Forgetting what is left over. Items still on the stack at the end are unresolved. For brackets that means the input is invalid; for next-greater it means the answer is the default.
  • Using if instead of while in the monotonic form. One new value can resolve many waiting positions.
  • Storing values when a distance is needed. Store indexes.
  • Choosing < or <= without thinking about equal values. Whether an equal value counts as "greater" changes the answer for inputs with repeats. Decide deliberately and test with repeated values.
  • Using shift and unshift. Those work on the front of the array and cost O(n) each. A stack only ever touches the end.

Practice problems

ProblemDifficultyTimeSpaceRead
Valid ParentheseseasyO(n)O(n)Short read: 5 min
Daily TemperaturesmediumO(n)O(n)Short read: 5 min
Largest Rectangle in HistogramhardO(n)O(n)Medium read: 8 min