Stacks
- Identify when a problem requires LIFO access by asking whether the most recently deferred item is always the first one resolved
- Build monotonic stacks where each element is pushed once and popped once, giving O(n) solutions to next-greater, span, and largest-rectangle problems
- Evaluate expressions with operator precedence by deferring lower-priority operators on the stack and resolving higher-priority ones immediately
- Derive a stack solution from scratch by deciding what gets deferred, what triggers resolution, what the stack stores, and when the answer is recorded
A stack holds items whose processing must wait for future context. Matching brackets, finding next-greater elements, evaluating expressions, and restoring nested state all reduce to the same structure: defer an item when it appears, then resolve it in reverse order when the resolving context arrives. The stack enforces that reverse order automatically.
What Is a Stack?
A stack exposes only its top element. Push adds to the top, pop removes from the top. The access order is LIFO: Last In, First Out.
The constraint is what makes stacks useful. Accessing elements in the middle requires first removing everything above them. This restriction maps directly to problems where the most recent item is always the first one needed.
Stack Operations (LIFO)
Empty stack. Ready for operations
The stack starts empty. Elements enter and exit from the top only.
Step 1 of 9
In code, a stack provides three operations, all O(1):
What Stacks Actually Do
A stack avoids rescanning by holding items that cannot be processed yet. Without a stack, two common problem types require repeated work.
Why Counting Fails for Bracket Matching
A first attempt at bracket validation counts openers and closers. If counts match, it must be valid.
This returns True for ")(", which is invalid. Tracking counts per bracket type still fails for "([)]", where counts are balanced but nesting is crossed.
Counting loses the sequence. The problem is not how many of each bracket type exist, but which specific opener the next closer should match. That depends on the order openers appeared. A data structure that preserves insertion order and returns the most recent item first solves this. That is a stack.
Why Brute Force Fails for Next Greater Element
For each element, find the first element to its right that is larger. The brute force approach scans rightward from every position.
This is O(n²) because each element independently scans the remainder of the array. Elements that could share the same answer are checked separately. A stack avoids this by holding all elements that have not found their answer yet. When a large element arrives, every waiting element smaller than it gets resolved in one pass.
Both problems share a structure. Something is encountered now but cannot be fully processed until future context arrives. The stack holds the deferred items and returns them in the order they need to be resolved.
How the Stack Stores Unresolved Candidates
Every stack problem reduces to deferred processing. Something is encountered now, but it cannot be fully resolved until later. The stack holds items waiting to be completed.
| Problem Type | What Gets Deferred | What Triggers Resolution |
|---|---|---|
| Bracket matching | Opening brackets | Matching closing bracket |
| Next Greater Element | Elements waiting for something larger | A larger element arrives |
| Decode String | Partial results at each nesting level | Closing bracket triggers multiply |
| Expression evaluation | Operands waiting for operator | Operator triggers computation |
For monotonic stack problems specifically, the stack stores candidates that have not found their answer yet. When a new value arrives, it resolves older candidates that it dominates by popping them. Popped values are finalized. Values that remain on the stack survive because the current value could not resolve them.
Why is resolution always LIFO? The most recently deferred item is the first one that can be resolved, because anything between it and the current position would have resolved it already if it could. The fact that it is still on the stack means nothing sufficient has arrived since it was pushed. The next sufficient value resolves it first, and then checks the item below.
An opener waits for its closer. A candidate waits for its next greater value. An operand waits for its operator. A nested context waits for its closing bracket. In each case, the most recently deferred item matches first because proper nesting, proximity, or precedence requires it. LIFO access is not arbitrary. It follows from the structure of the problem.
What the Stack Holds and Why
Each form of stack problem stores different things, but every stack has an invariant that must hold after each push and pop.
Matching
The stack holds unmatched openers. The top is always the most recent unmatched opener. When a closer arrives, it must match the top or the string is invalid. After processing all characters, an empty stack confirms every opener was matched.
Monotonic Stack
The stack holds unresolved candidates in sorted order (increasing or decreasing from bottom to top). The invariant is maintained by popping any element that the new arrival dominates. Values that survive are still waiting for their answer. Indices are usually stored instead of values because the answer must be recorded at a specific position in the result array.
Expression Evaluation
In RPN, the stack holds operands. Operators consume the top two operands immediately. In infix with precedence (Calculator II), the stack holds signed numbers. Higher-precedence operators (*, /) execute immediately by popping the top and computing. Lower-precedence operators (+, -) defer by pushing a signed number. At the end, summing the stack resolves all deferred operations.
State History
The stack holds snapshots of state at each nesting level. Pushing saves the current context before entering a new scope. Popping restores the parent context and attaches the resolved inner result. Each snapshot is a complete description of what was true before the nested scope began.
Matching and Pairing
This form applies when elements pair up in nested order. Signal words in the problem statement: valid, balanced, matching, nested.
Parentheses Matching
Validate "([{}])" for bracket matching
Opening brackets push to stack; closing brackets must match the top.
Step 1 of 11
How It Works
When an opener appears, it cannot be validated yet because what comes next is unknown. But if a closer appears, it must match the most recent unmatched opener. Any other opener would create a crossing pattern like "([)]" which violates proper nesting. This "most recent first" requirement is exactly LIFO.
Push openers and wait. When a closer arrives, check if the stack top matches. If it does, pop and continue. If it doesn't (or the stack is empty), the string is invalid.
The template has three key decisions:
- What is an opener? For brackets:
([{}. For HTML tags: the tag name inside<tag>. - What is a closer? The matching counterpart.
- How to verify match? Check that
stack[-1]equals the expected opener.
stack[-1] when the stack is empty. Input ")(" raises an IndexError at the first character. Always check if not stack before accessing the top.True instead of len(stack) == 0 misses unmatched openers. Input "((" has no matching error during iteration but is still invalid.Monotonic Stacks
This form applies when each element needs its nearest larger or smaller neighbor. Signal words: next greater, previous smaller, days until, span.
A monotonic stack maintains elements in sorted order: either always increasing from bottom to top, or always decreasing. This constraint is what makes nearest-element queries efficient.
Next Greater Element
Each element at index i waits for the first larger element to its right. Until that element arrives, the current element remains on the stack.
When a large element arrives, which waiting elements get answered? All the ones that are smaller than it. And the order in which they get answered follows LIFO: the most recent (smallest) waiting elements get popped first. When element C arrives, all elements smaller than C get popped, and C becomes their answer.
When element 4 arrives with stack [5, 3]: 4 > 3, so 3 is popped (its answer is 4). 4 < 5, so 4 pushes. Stack becomes [5, 4], still decreasing. The elements that would violate the ordering are exactly those whose answer has arrived. After removal, the invariant holds.
The popping rule enforces the invariant. When a new element arrives, everything smaller than it gets popped. The remaining elements are all larger. The new element becomes the top, maintaining the decreasing invariant.
Monotonic Decreasing Stack: Next Greater Element
Building a decreasing monotonic stack (largest at bottom)
Each element waits on the stack until something greater arrives.
Step 1 of 17
Store indices in the stack, not values. Indices are needed to record answers in the result array. The value is always accessible via nums[stack[-1]].
Why Monotonic Stacks Are O(n)
Ignore the nested loops. Count what happens to each element. Each element enters the stack exactly once when first encountered. Each element exits the stack at most once when something larger arrives.
Each element is pushed once and popped at most once, so the total number of operations across the entire array is at most 2n.
The inner while loop executes at most n times total across all iterations, not n times per iteration. Any individual iteration of the for loop may trigger multiple pops, but the total number of pops across the entire run cannot exceed n.
Previous Smaller Element
Previous queries are similar to next queries but with a key difference: the answer is known at push time, not pop time. When pushing element i, first pop everything greater than or equal to it. Whatever remains on top of the stack after popping is the nearest element to the left that is strictly smaller.
The stack maintains increasing order from bottom to top. When pushing element i, first pop everything >= nums[i]. Whatever remains on top (if anything) is the nearest element to the left that is strictly smaller than nums[i]. It survived on the stack because nothing between it and i was small enough to displace it.
Monotonic Increasing Stack: Previous Smaller Element
Building an increasing monotonic stack (smallest at bottom)
When we push, the stack top tells us the previous smaller element.
Step 1 of 17
| Query Type | Stack Order | Pop Condition | Answer Location |
|---|---|---|---|
| Next Greater | Decreasing | Current > Top | At pop time (current answers popped) |
| Next Smaller | Increasing | Current < Top | At pop time |
| Previous Greater | Decreasing | Current >= Top | At push time (stack top answers current) |
| Previous Smaller | Increasing | Current <= Top | At push time |
Largest Rectangle in Histogram
For each bar, we need to know how far left and right it can extend as the minimum height. A monotonic increasing stack gives us both boundaries. The width times the bar's height gives the area with that bar as the bottleneck.
Monotonic Stack Approach
Maintain an increasing stack. When a bar shorter than the stack top appears, pop and compute the area.
Width Formula
After popping the bar at index top, the rectangle extends from stack[-1]+1 to i-1. Width = i - stack[-1] - 1. Both boundaries are excluded.
Increasing vs Decreasing
The choice between increasing and decreasing stack depends on what triggers completion.
Ask: what are elements waiting for?
- Waiting for something larger: Pop when larger arrives. This gives you a decreasing stack (largest at bottom).
- Waiting for something smaller: Pop when smaller arrives. This gives you an increasing stack (smallest at bottom).
| Problem | Waiting For | Stack Type | Pop Condition |
|---|---|---|---|
| Next Greater Element | Larger element | Decreasing | Current > Top |
| Daily Temperatures | Warmer (larger) day | Decreasing | Current > Top |
| Stock Span | Larger price (to stop counting) | Decreasing | Current >= Top |
| Next Smaller Element | Smaller element | Increasing | Current < Top |
| Trapping Rain Water | Taller (larger) bar | Decreasing | Current > Top |
If popping when something smaller arrives, elements that remain are smaller than those that left. The remaining elements form an increasing sequence.
The stack type follows from what survives. When a large element arrives and pops smaller ones, smaller elements leave and larger ones stay. The stack holds the large elements. Decreasing. When a small element arrives and pops larger ones, larger elements leave and smaller ones stay. The stack holds the small elements. Increasing.
To check your reasoning: trace one element through the algorithm. If it gets popped by something larger, you are building a decreasing stack. If it gets popped by something smaller, you are building an increasing stack.
Expression Evaluation
This form applies when operands must wait for their operators, and inner expressions must evaluate before outer ones. Signal words: evaluate, calculator, polish notation, infix.
Reverse Polish Notation (RPN)
In RPN, operators come after their operands: 3 4 + means 3 + 4. This eliminates the need for parentheses and precedence rules.
In RPN, the hard work is already done. The expression 3 4 2 * + means "multiply 4 and 2, then add 3." The multiplication appears first in the token stream because it should happen first. By the time you see the +, the * has already computed its result. Evaluating RPN requires one pass: scan left to right, push numbers, apply operators to the top two numbers. No lookahead, no precedence checks.
a b -, the result is a - b, not b - a. The first value you pop is the right operand, because it was pushed more recently. The second pop gives the left operand.For "6 2 /": pop gives b=2, then a=6. Result is a/b = 6/2 = 3, not 2/6.
Reverse Polish Notation: ["3", "4", "2", "*", "+"]
Initialize: stack = []
In RPN, operands push onto stack. Operators pop two operands, compute, push result.
Step 1 of 18
Calculator Problems
The Basic Calculator family handles infix notation with operator precedence:
- Basic Calculator I: + - ( )
- Basic Calculator II: + - * / (no parentheses)
- Basic Calculator III: + - * / ( )
Basic Calculator II Strategy
Multiplication and division have higher precedence than addition and subtraction. In "3 + 4 * 2", 4 * 2 evaluates first, then 3 is added.
Addition and subtraction have lower precedence, so they must wait until all higher-precedence operations are resolved. Storing signed numbers on the stack for + or - defers the addition and subtraction. For * or /, immediate computation with the stack top is safe because no higher-precedence operation could intervene. At the end, summing the stack computes all the deferred additions and subtractions in order.
Track the previous operator. When a new operator appears, apply the previous one:
- Previous was + or -: push the number (with sign) to stack
- Previous was * or /: pop, compute, push result
int(a/b) truncates toward zero. a // b floors toward negative infinity. For -7 // 2, floor division gives -4, but the expected answer is -3. Use int(a/b) to match LeetCode's expected behavior.Basic Calculator II: "3+4*2"
Initialize: stack=[], num=0, sign="+"
Track previous operator. Apply it when we see the NEXT operator (or end).
Step 1 of 19
State History
This form applies when processing creates nested contexts that must be restored in reverse order. Signal words: undo, back, nested structure, track history.
Each stack entry captures state at push time. Popping restores it. Undoing in arbitrary order would violate state dependencies. State B was created by modifying State A. The modification assumed A existed. To undo B, you need A's context. But if you tried to undo A first while B still exists, you would be removing the foundation that B was built on. Each state depends on the one before it. The dependency ordering is LIFO.
Decode String: Nested State
Problem: Given "3[a2[c]]", return "accaccacc".
When "[" appears, a nested context begins. Push the current state (partial result and multiplier) and reset the accumulator. When "]" appears, pop the saved state, multiply the inner result, and append.
Decode String: Stack State History
Initialize: stack=[], current_string="", current_num=0
Stack stores (previous_string, multiplier) when entering nested brackets.
Step 1 of 18
Min Stack: O(1) getMin
Min Stack pairs each value with the running minimum at the time it was pushed. When an element is popped, the previous minimum is automatically the minimum stored with the element now on top. No rescanning is needed.
When Stacks Break
Stacks require LIFO access. When the next item to process is not the most recently added one, a stack is the wrong structure.
| Requirement | Why Stack Fails | Use Instead |
|---|---|---|
| Process in discovery order (FIFO) | The oldest item needs to come out first, but the stack returns the newest | Queue |
| Access both oldest and newest | The stack only exposes the top | Deque |
| Random access by key | Finding an item in the middle requires popping everything above it | Hash map |
| Maintain sorted access | The stack is ordered by insertion time, not by value | Heap or BST |
| Aggregate state across a range | The stack does not track a running sum, frequency, or count of a contiguous window | Sliding window or prefix sum |
The diagnostic question: when you retrieve a deferred item, is it the most recently deferred? If the answer is sometimes no, the problem does not have LIFO structure. BFS processes states in FIFO order. Sliding window queries need access to the entire range, not just the top. Top-k problems need the smallest or largest available element, not the most recent.
Stack vs Similar Patterns
| Comparison | Stack | Alternative | When to Choose |
|---|---|---|---|
| Stack vs Queue | LIFO: most recent item first | FIFO: oldest item first | Use queue when processing order must match discovery order (BFS, scheduling) |
| Monotonic Stack vs Sorting | Preserves position, gives nearest neighbor in O(n) | Gives global order but loses original positions | Use sorting when global rank matters. Use monotonic stack when you need nearest-neighbor answers while preserving the left-to-right scan |
| Stack vs Recursion | Explicit control over the deferred items | Implicit call stack manages deferred frames | Use explicit stack when recursion depth may exceed limits, when you need to inspect the stack contents, or when iterative control is required |
| Stack vs Deque | Access only the top (one end) | Access both ends | Use deque when you need to expire old items from the front while adding new items at the back (sliding window maximum) |
Debugging Stack Code
Use these checks when your stack code fails hidden test cases.
Is the stack empty before accessing the top?
Always check if stack before accessing stack[-1] or calling stack.pop().
Did you verify the stack is in the expected final state?
After processing all input, verify the stack is empty (matching), fully resolved (monotonic), or contains the final answer (expression evaluation).
Is the width formula correct for histogram problems?
In histogram problems, both boundaries are excluded from the rectangle. The left boundary is the index below the popped element, and the right boundary is the current index.
Is the comparison strict or non-strict?
Check whether the problem wants strict inequality (>) or non-strict (>=). This affects whether equal elements pop each other.
Is the operand order correct for non-commutative operations?
First pop gives the right operand. Second pop gives the left operand. This matters for subtraction and division.
Deriving the Stack Solution
When a new problem involves deferred processing but you are not sure how to set up the stack, use these five questions to derive the structure.
| Step | Question | Bracket Matching | Next Greater Element | Calculator II |
|---|---|---|---|---|
| 1 | What is being deferred? | Opening brackets | Elements waiting for larger | Signed numbers for +/- |
| 2 | What triggers resolution? | Matching closer arrives | Larger element arrives | End of string or next operator |
| 3 | Is resolution LIFO? | Yes: most recent opener matches first | Yes: smallest waiting element resolves first | Yes: deferred sums resolve in order after all *// done |
| 4 | What does the stack store? | Characters (opener type) | Indices (to write result at position) | Signed numbers (value with sign) |
| 5 | When is the answer recorded? | Validity check on pop + final empty check | At pop time: current value is the answer for popped index | At the end: sum of stack is the final result |
If step 3 is "no" (the most recently deferred item is not the first one resolved), a stack is the wrong data structure. Consider a queue, heap, or hash map instead.
For monotonic stack problems, add one more question: should the stack be increasing or decreasing? If elements are resolved when something larger arrives, the remaining elements are larger. Decreasing stack. If elements are resolved when something smaller arrives, the remaining elements are smaller. Increasing stack.
Practice Problems
Matching
| Problem | Difficulty | Approach |
|---|---|---|
| Valid Parentheses | Easy | Most recent opener must match first. Check before accessing stack. |
| Minimum Remove to Make Valid | Medium | Track indices of unmatched brackets. Two passes: find, then remove. |
| Longest Valid Parentheses | Hard | Stack stores index of last unmatched. Length = current - stack top. |
| Basic Calculator | Hard | Parentheses create nested contexts. Push state on "(", restore on ")". |
| Asteroid Collision | Medium | Stack holds right-moving asteroids. Resolve on collision. |
Monotonic Stack
| Problem | Difficulty | Approach |
|---|---|---|
| Next Greater Element I | Easy | Build answer map with decreasing stack first. |
| Daily Temperatures | Medium | Store indices, not values. Answer is index difference. |
| Online Stock Span | Medium | Stack stores (price, span). Accumulate span when popping. |
| Maximal Rectangle | Hard | Build histogram row by row. Apply largest rectangle to each. |
| Trapping Rain Water | Hard | Decreasing stack. Pop when taller found. Water bounded by min(walls). |
Expression Evaluation
| Problem | Difficulty | Approach |
|---|---|---|
| Evaluate Reverse Polish Notation | Medium | First pop = right operand. Push result back. |
| Basic Calculator II | Medium | Process */ immediately. Defer +- by pushing signed numbers. |
| Basic Calculator III | Hard | Recursion for parentheses or use two stacks. |
State History
| Problem | Difficulty | Approach |
|---|---|---|
| Decode String | Medium | Push (previous_string, multiplier) on "[". Restore on "]". |
| Design Browser History | Medium | Two stacks: back and forward. Move between them. |
Reference Templates
Compact code shapes for recovery. Each template shows the core loop structure for one form.
Matching
Use when closers must match the most recent unmatched opener.
Next Greater Element (Monotonic Stack)
Use when elements wait for the next greater or smaller value.
Previous Smaller Element
Use when the answer is known at push time after popping invalid candidates.
Largest Rectangle
Use when each bar needs the nearest smaller boundary on both sides.
RPN Evaluation
Use when operators consume the most recent operands.
Calculator II
Use when multiplication and division resolve immediately while addition and subtraction are deferred.
Decode String
Use when nested contexts must be restored on closing brackets.
Pattern Recap
Matching stacks hold unmatched openers. Each closer must match the most recent opener, or the structure is invalid. After processing, an empty stack confirms every opener was matched.
Monotonic stacks hold unresolved candidates in sorted order. A new value pops candidates it dominates, finalizing their answer. Values that survive have not found their answer yet. The answer is recorded at pop time for "next" queries and at push time for "previous" queries.
Expression stacks hold operands waiting for operators. In RPN, precedence is already encoded in token order, so evaluation is a single pass. In infix with precedence, lower-precedence operations are deferred while higher-precedence operations execute immediately.
State history stacks hold snapshots at each nesting level. Pushing saves the current context. Popping restores the parent context and attaches the resolved inner result.
Rebuilding the Pattern
When a stack problem feels unclear, start with what is being deferred. Something must be encountered now but processed later. Identify exactly what that something is: an opener, an element waiting for a larger neighbor, an operand, a partial result at a nesting level.
Then identify what triggers resolution. For matching, the trigger is a closer. For monotonic queries, the trigger is a value that dominates the waiting candidates. For expressions, the trigger is an operator. For nested state, the trigger is a closing bracket. The trigger tells you when to pop.
Confirm that the resolution order is LIFO. The most recently deferred item should always be the first one resolved. If this is not true, the problem does not have stack structure. If it is true, the stack will enforce the correct resolution order automatically.
Decide what to store. If the result must be placed at a specific position, store indices. If you need to restore a snapshot, store tuples of state. If you only need to compare values, store values directly.
Finally, decide when the answer is safe to record. In "next" monotonic queries, the answer is recorded when a candidate is popped. In "previous" queries, the answer is recorded when a new element is pushed and the stack top provides the answer. In matching, validity is determined both at each pop (does the closer match the opener?) and at the end (is the stack empty?). In expressions, the final answer is the value remaining on the stack after all tokens are processed.
Check Your Understanding
Use these questions to check whether you can reason through the pattern without looking at the template.
Ready to test it?
12 questions across all four stack patterns.
Practice this pattern
Apply the guide to complete interview problems with explanations and code.
Learn Stacks in a guided sequence
The Interview Course connects this pattern to its prerequisites, worked lessons, and progressively harder problems.