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
whileinside theforlooks like O(n²), but each index is pushed once and popped at most once. However the pops are distributed, there are at mostnof 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 > 0before 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
ifinstead ofwhilein 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
shiftandunshift. Those work on the front of the array and cost O(n) each. A stack only ever touches the end.
Practice problems
| Problem | Difficulty | Time | Space | Read |
|---|---|---|---|---|
| Valid Parentheses | easy | O(n) | O(n) | Short read: 5 min |
| Daily Temperatures | medium | O(n) | O(n) | Short read: 5 min |
| Largest Rectangle in Histogram | hard | O(n) | O(n) | Medium read: 8 min |