These are my data structures and algorithms notes, cleaned up into nineteen posts, one pattern at a time. This one covers the stack: the plain stack for nesting and “most recent first” work, and the monotonic stack that finds the nearest bigger or smaller element in a single pass.
A stack is the data structure for work that finishes in the reverse order it started. Open a folder, open a subfolder, and you have to leave the subfolder before you can leave the folder. Anything shaped like that, nesting, undo, “the latest unfinished thing”, is a stack problem, even when the statement never says so.
In the order this series follows, Stack comes straight after Arrays & Hashing, next to Two Pointers. It is a leaf: no later topic depends on it, but the call stack behind every recursive tree and graph traversal later in the series is the same structure. The prerequisite here is Stacks. Half of this topic’s problem list also needs the monotonic stack, so it gets a second module of its own.
How to use this post: the method. Checkpoints have no answers on the page: work them out, then open the linked chat to have your answer checked.
Stacks
Foundation
Think of a stack of plates. You put a plate on top, and you take a plate off the top. You never pull one from the middle. That restriction is the whole idea: last in, first out (LIFO).
A better mental model for interviews: a stack is a to-do list where you must finish the newest item before you can get back to the older ones. Whenever a problem has “the thing I need to deal with next is the most recent one I haven’t dealt with yet”, a stack holds exactly those unresolved things, in the order you’ll need them.
It solves three families of problems:
- Nesting. Inner things must close before outer things. Directories, function calls, anything with an open and a matching close.
- Most recent first. An action applies to the latest item still pending: undo, backspace, “cancel the previous one”.
- Reversal. Push a sequence, pop it, and it comes back reversed.
In Part 2 the dynamic array gave O(1) amortized append and pop at its end. A stack is just a dynamic array that you promise to touch only at that end. In Python you don’t need a class; a list already is one.
| Operation | Python | Cost |
|---|---|---|
| push | stack.append(x) |
O(1) amortized (recalled) |
| pop | stack.pop() |
O(1) (recalled) |
| peek at top | stack[-1] |
O(1) |
| is empty? | not stack |
O(1) |
| size | len(stack) |
O(1) |
The wrong end is expensive: stack.pop(0) and stack.insert(0, x) shift every other element, O(n) each (recalled). If you ever need both ends, that’s collections.deque, not a stack.
Mechanics
The worked example for this module is simplifying a Unix-style path. Given "/a/b/../c/./d/..", return the canonical path. A name means “go into that directory”, .. means “go up one level”, . means “stay here”, and repeated slashes mean nothing.
Step by step:
- Split on
/:['', 'a', 'b', '..', 'c', '.', 'd', '..']. The empty strings come from the leading slash (and would come from any//). - Walk the parts left to right, keeping a stack of directory names from the root down to where you currently are.
- A name: push it. You went one level deeper.
..: pop. You left the current directory..or empty: do nothing.- At the end, the stack, read bottom to top, is the path.
The invariant: after each part, the stack holds exactly the directories from the root to the current directory, root at the bottom, current directory on top.
Why popping is safe. .. can only ever mean “leave the directory I’m in right now”, and the directory you’re in right now is always the top of the stack. After a and b the stack is [a, b]. The .. has to remove b, never a, because you can’t leave a while you’re still inside b. That’s nesting: the newest unresolved item is the only one that can be resolved next, and a stack puts it exactly where you can reach it in O(1).
The boundary case. .. at the root (an empty stack) goes nowhere: "/../x" is "/x". So the pop needs a guard. Without it, Python raises IndexError on [].pop() (recalled).
Diagram
The stack after each part of "/a/b/../c/./d/..", read left to right and then along the second row:
.. just popped; empty strings and . leave the stack alone. The final stack [a, c] gives "/a/c".Look at the two .. panels. Each one removes whatever was pushed most recently and not yet removed (b, then d). Neither ever touches a.
Implementation
def simplify_path(path: str) -> str:
stack = [] # directory names from the root (stack[0]) to the current directory (stack[-1])
for part in path.split("/"):
# "/a/b/../c/./d/..".split("/") -> ['', 'a', 'b', '..', 'c', '.', 'd', '..']
if part == "" or part == ".":
# "" comes from the leading "/" and from any "//"; "." means "stay here".
# Neither changes the current directory, so the stack is left alone.
continue
if part == "..":
# ".." leaves the current directory, which is stack[-1]:
# with stack == ['a', 'b'], ".." must drop 'b', leaving ['a'].
# With an empty stack we are at the root, and "/../x" must give "/x",
# so skip the pop (recalled: [].pop() raises IndexError).
if stack:
stack.pop()
continue
stack.append(part) # a real name: one level deeper, so it becomes the new top
# stack is ordered root -> current, so joining bottom to top rebuilds the path.
# For the example the final stack is ['a', 'c'] -> "/a/c".
return "/" + "/".join(stack)
Run against the worked example and some edges:
| Input | Output |
|---|---|
"/a/b/../c/./d/.." |
"/a/c" |
"/../x" |
"/x" |
"/" |
"/" |
"/home//foo/" |
"/home/foo" |
"/a/../../b/./c/" |
"/b/c" |
Complexity. With n = len(path): O(n) time. The split and the join are O(n), and each part is pushed at most once and popped at most once. O(n) extra space for the parts and the stack.
Recognition
Signals that a stack is the right tool:
- The input has nesting or matching: something opens, something later closes it, and closes happen innermost first.
- An operation acts on the most recent pending item: “undo”, “cancel the previous”, “delete the last”, “combine the last two”.
- You scan left to right and each new element either resolves some earlier waiting element or joins the waiting set.
- A recursive solution exists and you want an iterative one. The call stack is a stack; you can hold it yourself.
When not to use one:
- You need the oldest pending item first (arrival order, level-by-level processing). That’s a queue.
- You need the smallest or largest of everything pending, not the newest. That’s a heap (Heap / Priority Queue), or a running variable if nothing is ever removed.
- You need to remove from both ends. That’s a deque.
In this topic’s list, the signals show up plainly: Valid Parentheses has nesting, Evaluate Reverse Polish Notation has operators that act on the most recent operands, and Min Stack asks you to build on the stack interface itself.
Pitfalls
- Pop or peek on an empty stack. Always guard:
if stack:beforestack.pop(), andwhile stack and stack[-1] ...so theandshort-circuits beforestack[-1]is evaluated (recalled:andevaluates left to right and stops at the first falsy operand). - Forgetting what’s left at the end. When the loop ends, a non-empty stack means items that were never resolved. Decide explicitly whether that’s the answer (like the path), an error, or items that get a default value.
- Using the wrong end.
pop(0)quietly turns an O(n) algorithm into O(n²). - Pushing the wrong thing. Push whatever you’ll need at pop time. If you’ll need a position or a distance later, push the index, not the value.
- Building strings inside the loop. Keep a list and
"".joinit once at the end rather than rebuilding a string on every step.
Active Recall
1. In the worked example, what is the stack right after processing c, and why was a never popped even though two .. parts appeared?
2. What should "/a/../../b" return, and what line in the implementation makes that happen?
3. Why do we use append and pop() on the right end of the list instead of insert(0, x) and pop(0)? Both are “a stack”.
4. Suppose you only needed the depth of the final directory (for the example, 2), not its path. What could replace the stack?
Answer out loud or on paper first.
Mini-task
Judgment call: every problem in this list arrives already labeled “Stack”, and none requires discovering the plain push/pop discipline from an unlabeled statement, so this module’s mechanics wouldn’t otherwise be exercised independently; the checkpoint stays.
A string is reduced by repeatedly deleting two adjacent, equal characters, until no such pair remains. For "abbaca": delete "bb" to get "aaca", then delete "aa" to get "ca". Return the final string. The input can be up to 10⁵ characters. (The problem guarantees the final string is the same whichever pair you delete first.)
Before opening the chat, write down: the observation, the approach, why it’s correct, the complexity.
Transfer test
You’re building a text editor with three commands: type some text, undo the last change, redo the last undone change. Would you use a stack? Why?
Monotonic Stack
Why it’s here: Daily Temperatures and Largest Rectangle In Histogram both need, for each element, the nearest element to one side that is bigger or smaller, and the Stacks lesson alone doesn’t give you the pop rule that makes that O(n) instead of O(n²). The problems below also need this.
Foundation
Stand at the right end of a street of buildings and look left. A tall building hides every shorter building behind it. If a tall building goes up at position i, every shorter building to its left becomes irrelevant to anyone standing further right: they will look left, hit building i first, and never see the shorter ones behind it.
That’s the entire trick. A monotonic stack is a normal stack plus one rule: before pushing a new element, pop everything it hides. What remains on the stack is always sorted (hence “monotonic”), and it’s exactly the set of elements that could still be the answer for something to the right.
The problem it solves: for each index i, find the nearest index j to one side where nums[j] is bigger (or smaller) than nums[i]. The brute force scans outward from each i until it finds one. On an increasing array like [1, 2, 3, ..., n], looking left for something bigger never succeeds, so that’s 0 + 1 + … + (n−1) = n(n−1)/2 comparisons, O(n²).
Mechanics
Worked example: previous greater element. For each i, find the index of the nearest j < i with nums[j] > nums[i] (strictly), or −1 if none.
nums = [5, 3, 1, 3, 4, 2]
The loop, for each index i with value x:
- While the stack is non-empty and the value at its top is ≤ x, pop.
- If the stack is non-empty, the top is the answer for i. Otherwise the answer is −1.
- Push i.
Invariant 1 (the sorted part). Values at the stack’s indices are strictly decreasing from bottom to top. Step 1 removes everything ≤ x, so whatever is left on top is > x, and pushing x keeps the order strict.
Invariant 2 (the shadow). For two neighbouring stack entries a (below) and b (above), every index strictly between a and b has a value ≤ nums[b]. Those indices were all gone by the time b was pushed: removed by b itself, or by an index that b (directly or through a chain of pops) then removed. Each pop only removes values ≤ the popper’s value, so the chain ends at a value ≤ nums[b].
Why popping is safe. Suppose i pops j. Then j < i and nums[j] ≤ nums[i]. Take any future index k > i. If nums[j] > nums[k], then nums[i] ≥ nums[j] > nums[k], so i also qualifies as a previous greater for k, and i is closer to k than j is. So j can never again be the nearest answer for anyone. Removing it loses nothing.
Why the top is the answer. After step 1, the top is > x (it wasn’t popped). By invariant 2, every index between the top and i was either just popped (so ≤ x) or sits under the shadow of something that was just popped, which was ≤ x. So nothing between them is > x, and the top is the nearest one that is.
Why it’s O(n) despite the nested while. Each index is pushed exactly once and popped at most once. Over the whole run, the while loop body executes at most n times in total, not n times per i. On the example: 6 pushes and 3 pops.
The same loop gives a second answer for free. When i pops j, i is the first index to the right of j with a value ≥ nums[j]: j’s next greater-or-equal element. In the example, index 3 pops indices 2 and 1, and index 4 pops index 3, so the next greater-or-equal indices are [-1, 3, 3, 4, -1, -1]. Indices left on the stack at the end (0, 4, 5) were never popped, so they have none.
The four common variants all come from this one loop. Each was checked against a brute-force scan on 2,000 random arrays with duplicates:
| You want, for each i | Scan | Pop while nums[stack[-1]] is |
Read the answer |
|---|---|---|---|
| previous greater | left to right | <= x |
top after popping, for i |
| previous smaller | left to right | >= x |
top after popping, for i |
| next greater | left to right | < x |
at pop time: the popped index’s answer is i |
| next smaller | left to right | > x |
at pop time: the popped index’s answer is i |
“Greater” variants keep a decreasing stack (non-increasing when ties are allowed to stay); “smaller” variants keep an increasing one. The strictness of the pop condition decides how ties behave, and the table’s conditions give strictly greater and strictly smaller answers.
Diagram
The i = 3 panel is the interesting one. The new 3 hides the 1 at index 2 (1 ≤ 3) and the older 3 at index 1 (3 ≤ 3, and we want strictly greater). It stops at the 5 at index 0, which becomes the answer. In every panel, the stack values read as a strictly decreasing sequence from bottom to top.
Implementation
def previous_greater(nums: list[int]) -> list[int]:
"""answer[i] = index of the nearest j < i with nums[j] > nums[i], or -1 if none."""
answer = [-1] * len(nums) # -1 remains wherever nums[0..i-1] has nothing > nums[i]
stack = [] # indices, with nums[stack[0]] > nums[stack[1]] > ... > nums[stack[-1]]
for i, x in enumerate(nums):
# Pop every index j with nums[j] <= x. Such a j lies left of i and nums[j] <= nums[i],
# so for any later k with nums[j] > nums[k], nums[i] > nums[k] as well and i is closer.
# [5, 3, 1, 3, 4, 2] at i = 3 (x = 3): pops index 2 (1 <= 3), then index 1 (3 <= 3),
# then stops at index 0 because 5 <= 3 is false.
while stack and nums[stack[-1]] <= x:
stack.pop()
if stack:
# stack[-1] survived the loop, so nums[stack[-1]] > x, and every index strictly
# between stack[-1] and i holds a value <= x. At i = 3: stack[-1] = 0 (value 5),
# and indices 1..2 hold 3 and 1, both <= 3. So answer[3] = 0.
answer[i] = stack[-1]
# else: an empty stack means no value > x in nums[0..i-1].
# At i = 0 the stack starts empty, so answer[0] stays -1.
stack.append(i) # i may be the previous greater for some later index
return answer
Run against the worked example and edges:
| Input | Output |
|---|---|
[5, 3, 1, 3, 4, 2] |
[-1, 0, 1, 0, 0, 4] |
[] |
[] |
[1] |
[-1] |
[1, 2, 3] |
[-1, -1, -1] |
[3, 2, 1] |
[-1, 0, 1] |
[2, 2, 2] |
[-1, -1, -1] |
Complexity. With n = len(nums): O(n) time, because there are n pushes and at most n pops across the whole loop. O(n) extra space: a strictly decreasing input like [3, 2, 1] never pops, so the stack ends holding all n indices.
Recognition
Signals:
- The words nearest, next, previous, first … to the left/right combined with bigger, smaller, warmer, taller, shorter.
- “How far can this element extend before something blocks it?” The blocker is the nearest smaller (or bigger) element on each side.
- A brute force whose inner loop scans outward and stops at the first element that beats the current one. That early stop is the fingerprint.
- Something that gets blocked or absorbed by what’s ahead of it.
In this topic’s list: Daily Temperatures asks about the next warmer day, Largest Rectangle In Histogram asks how far each bar can extend before hitting a shorter one, and Car Fleet has cars that can’t pass the one ahead of them.
When not to use it:
- You need the max or min over everything to one side, not the nearest qualifying element. A running max or min is simpler (see the transfer test).
- You need the max or min of a sliding window. Old elements must also leave from the bottom when they fall out of the window, so that’s a monotonic deque, covered in Sliding Window.
- You need the k-th largest, or the min of a set that changes arbitrarily. That’s a heap.
Pitfalls
- Strict versus non-strict.
<=versus<in the pop condition decides what happens with duplicates. On the example, popping only on<gives previous greater-or-equal,[-1, 0, 1, 1, 0, 4]: index 3 would stop at the earlier 3. Decide which one the problem wants before writing the condition. - Pushing values instead of indices. With values you can’t compute a distance, a width, or write into
answer[j]at pop time. Push indices and look values up innums. ifinstead ofwhile. One new element can hide many older ones (index 3 popped two). A singleifpops at most one and breaks the invariant.- Leftovers. Indices still on the stack at the end never found their “next” element. Initialize
answerwith a default (−1, n, 0, whatever the problem says) so they’re handled without a second loop. - Believing it’s O(n²). A
whileinside aforlooks quadratic. Count pushes and pops instead of loop nesting.
Active Recall
1. For nums = [5, 3, 1, 3, 4, 2], what are the stack’s indices and values right after processing i = 4, and which invariant do they show?
2. At i = 3, index 1 (value 3) is popped by the new value 3. Why is it safe to throw index 1 away permanently, for every future index?
3. Change the pop condition from <= x to < x. What does the answer array become for the example, and what does it now mean?
4. With the original <= loop, which indices get popped by index 3 and by index 4? What does being popped tell you about those indices, as opposed to their “previous greater”?
5. Someone says the loop is O(n²) because of the while inside the for. Give the argument that it’s O(n), using the example’s counts.
Answer out loud or on paper first.
Mini-task
Judgment call: Largest Rectangle In Histogram requires deriving from scratch what a pop means for the popped bar, so it exercises this technique independently; skipping this checkpoint.
Transfer test
For each index of an array, you want the largest value anywhere to its right (or nothing for the last index). For [5, 3, 1, 3, 4, 2] that’s [4, 4, 4, 4, 2, None]. Would you use a monotonic stack? Why?
Integration
How the two modules make up the topic. Every problem in this list is about unresolved items and the event that resolves them. The plain stack handles the case where the item to resolve is always the most recent one (nesting, the latest operands, the latest action). The monotonic stack handles the case where one new element can resolve many waiting ones at once, because it’s bigger or smaller than all of them. Both do all their work in a single left-to-right pass, and both are O(n) for the same reason: each item is pushed once and popped at most once, and the pop is where the answer gets decided.
Choosing between competing approaches.
| If the problem needs … | Reach for | Why not a stack |
|---|---|---|
| The most recent pending item, nesting, undo | Stack | It is a stack |
| Nearest bigger or smaller element to one side | Monotonic stack | It is one |
| The oldest pending item first, level by level | Queue (deque) |
LIFO gives the wrong order |
| Max or min of a moving window | Monotonic deque | Old items must also leave from the bottom |
| Max or min over everything so far | Running variable | Nothing is ever removed, so no structure is needed |
| Smallest or largest of a changing set, k-th largest | Heap | A stack only exposes the newest, not the extreme |
| A pair in a sorted array | Two pointers | No pending items at all |
A recognition checklist for an unfamiliar problem.
- As I scan, does each element leave something pending that a later element will resolve?
- Is the thing resolved always the most recent pending item? Then a plain stack.
- Can one new element resolve several pending items at once because it beats them all on size? Then a monotonic stack, and decide: previous or next, greater or smaller, strict or not.
- Do I need to know which items are pending, or only how many? If only how many, a counter may replace the stack.
- What goes on the stack: the value, the index, or both? If the answer involves distance, width or position, it’s the index.
- What happens to items still on the stack when the input ends?
- Sanity check: can I bound the total number of pops by n? If yes, it’s O(n).
The problems
Work these with the solving cycle from Part 1: a 15-minute struggle, one key sentence per problem, spaced repetition. During the struggle for stack problems, ask: what is pending, what event resolves it, and does it resolve only the newest item or several at once? Draw the stack after each element of a five-element example before writing code.
6 problems · 1 easy · 4 medium · 1 hard · tracker spreadsheet (.xlsx)
| # | Problem | Difficulty | Coach |
|---|---|---|---|
| 1 | Valid Parentheses | Easy | ChatGPT · Claude |
| 2 | Min Stack | Medium | ChatGPT · Claude |
| 3 | Evaluate Reverse Polish Notation | Medium | ChatGPT · Claude |
| 4 | Daily Temperatures | Medium | ChatGPT · Claude |
| 5 | Car Fleet | Medium | ChatGPT · Claude |
| 6 | Largest Rectangle In Histogram | Hard | ChatGPT · Claude |
Take this lesson as a live session
If you’d rather be taught this interactively, with the coach waiting for your answers, open the full lesson prompt in a chat.