Stack Practice Problems
How to Use This Problem List
Stack problems form one of the tightest pattern families in DSA interviews. Every stack problem reduces to one of six recognisable patterns — and once you recognise the pattern, the implementation follows almost mechanically.
The goal of practice is not to memorise each solution. It is to recognise the structure within the first two minutes of reading: "This needs a stack because the most recently opened thing must be resolved first" or "This needs a monotonic stack because I'm looking for the nearest greater element."
Practice by pattern. Solve five problems from one pattern before moving to the next. After two weeks of deliberate practice, pattern recognition becomes automatic.
Pattern 1: Basic Stack — LIFO and Matching
The fundamental use of a stack: push things on arrival, pop things when their match or resolution arrives. The most recently pushed element is always resolved first.
| Problem | Difficulty | Recognition Clue | Key Insight |
|---|---|---|---|
| Valid Parentheses | Easy | "matching brackets", "balanced" | Push openers, pop and match on closers, valid iff stack empty |
| Min Stack | Medium | "O(1) getMin" | Auxiliary min-stack — push min(val, minStack.top()) in sync |
| Implement Stack using Queues | Easy | "implement stack with queues" | Two queues OR one queue with rotation after every push |
| Implement Queue using Stacks | Easy | "implement queue with stacks" | Two stacks — input and output; lazy transfer when output is empty |
| Make the String Great | Easy | "remove adjacent opposite-case pairs" | Stack — push char; pop if top is same letter different case |
| Remove All Adjacent Duplicates | Easy | "remove adjacent equal chars repeatedly" | Stack — pop if top equals current char, else push |
| Backspace String Compare | Easy | "#means backspace", "are strings equal" | Simulate with stack — push char, pop on '#' |
| Baseball Game | Easy | "C undoes, D doubles, + sums last two" | Stack of scores, apply each operation directly |
Complexity target: O(n) time, O(n) space.
Recognition signal: The problem involves matching, undoing, or resolving the most recent unresolved item. Nesting or sequential dependency where the latest thing determines what happens next.
Pattern 2: Monotonic Decreasing Stack — Next Greater
Push indices onto the stack. Pop when a larger element arrives — the popped element's "next greater" is the element that caused the pop. Remaining elements in the stack at the end have no greater element.
| Problem | Difficulty | Recognition Clue | Key Insight |
|---|---|---|---|
| Next Greater Element I | Easy | "find next greater in a second array" | Precompute NGE with monotonic stack, store in map |
| Next Greater Element II | Medium | "circular array" | Traverse 2× (indices 0 to 2n-1), use i % n, push only first pass |
| Daily Temperatures | Medium | "days until warmer" | Same as NGE but answer is i - top (distance, not value) |
| Online Stock Span | Medium | "consecutive days ≤ today" | Pop on >=, span = i - new_top or i + 1 |
| Next Greater Node in Linked List | Medium | "linked list, find next greater value" | Convert to array first, then apply NGE template |
| Number of Visible People in Queue | Hard | "count visible people to the right" | Pop shorter people — each pop = one visible person |
| Sum of Subarray Minimums | Hard | "sum of min of every subarray" | Two monotonic passes: previous smaller left, next smaller right |
| 132 Pattern | Hard | "find i < j < k with nums[i] < nums[k] < nums[j]" | Monotonic decreasing stack — track candidate k value |
Complexity target: O(n) time, O(n) space.
Recognition signal: "next/previous greater/smaller," "how many days/steps until," "consecutive span." The answer for each element depends on the first element to its right (or left) that satisfies a size condition.
Pattern 3: Monotonic Increasing Stack — Next Smaller and Boundaries
Pop when a smaller element arrives. The popped element's "next smaller" is the element that caused the pop. Used when you need left and right boundaries for each element simultaneously.
| Problem | Difficulty | Recognition Clue | Key Insight |
|---|---|---|---|
| Next Smaller Element | Easy | "find next smaller to the right" | Increasing stack — pop when arr[i] < arr[top] |
| Previous Smaller Element | Easy | "nearest smaller to the left" | Increasing stack — at each push, top is the previous smaller |
| Largest Rectangle in Histogram | Hard | "largest rectangle in bars" | Pop on smaller, width = i - stack.top() - 1, sentinel 0 at end |
| Maximal Rectangle | Hard | "maximal rectangle in binary matrix" | Apply histogram algorithm row by row |
| Trapping Rain Water | Hard | "how much water trapped between bars" | Pop bottom, left = new top, right = current; min(left,right)-bottom × width |
| Sum of Subarray Ranges | Medium | "sum of (max - min) of every subarray" | Four monotonic passes: NGE, NSE, PGE, PSE boundaries |
| Remove K Digits | Medium | "remove k digits to make smallest number" | Monotonic increasing stack — pop when larger digit can be removed |
| Shortest Unsorted Continuous Subarray | Medium | "find subarray to sort so whole array is sorted" | Find left/right boundaries using monotonic properties |
Complexity target: O(n) time, O(n) space.
Recognition signal: "nearest smaller," "left and right boundary," "largest area," "water trapped." Problems where you need to find the extent to which each element dominates its neighbours.
Pattern 4: Expression Evaluation
Stack-based arithmetic — postfix evaluation, infix-to-postfix, prefix evaluation, and direct infix computation with two stacks.
| Problem | Difficulty | Recognition Clue | Key Insight |
|---|---|---|---|
| Evaluate Reverse Polish Notation | Medium | "postfix", "RPN", "tokens with operators" | Push numbers, on operator pop two, apply, push result; b popped first (right operand) |
| Basic Calculator | Hard | "evaluate infix with +, -, (, )" | Stack of partial results and signs; push on (, pop and apply on ) |
| Basic Calculator II | Medium | "evaluate with +, -, *, / no parentheses" | Push adjusted values: + push, - push negated, */* pop and push product/quotient |
| Basic Calculator III | Hard | "full arithmetic with all operators and parens" | Recursive parser OR two-stack infix evaluation |
| Expression Add Operators | Hard | "insert +, -, * between digits to reach target" | DFS with running total and last multiplicand (for backtracking *) |
| Different Ways to Add Parentheses | Medium | "all possible results from different groupings" | Divide and conquer on each operator |
| Minimum Cost Tree from Leaf Values | Medium | "build tree from array, minimize sum of non-leaves" | Monotonic stack — find optimal left-right split iteratively |
| Decode String | Medium | "k[string]" repeated k times | Stack of (count, currentString); push on [, pop and multiply on ] |
Complexity target: O(n) or O(n²) depending on variant. Postfix evaluation and Basic Calculator II are O(n) time O(n) space.
Recognition signal: "evaluate expression," "arithmetic with precedence," "brackets change grouping," "expand encoded string." Any problem where a number controls how many times a subsequent block is processed.
Pattern 5: Iterative DFS and Simulation
Replace recursion with an explicit stack to simulate depth-first traversal, function call behaviour, or any process that requires tracking "pending work" at multiple nesting levels.
| Problem | Difficulty | Recognition Clue | Key Insight |
|---|---|---|---|
| Number of Islands (iterative) | Medium | "DFS without recursion" | Stack of (row, col) coordinates — push unvisited neighbours |
| Binary Tree Inorder Traversal | Easy | "iterative inorder" | Push left spine, pop and visit, then push right subtree |
| Binary Tree Preorder Traversal | Easy | "iterative preorder" | Push right then left — left is popped (visited) first |
| Binary Tree Postorder Traversal | Medium | "iterative postorder" | Modified preorder (root-right-left) then reverse result |
| Flatten Binary Tree to Linked List | Medium | "flatten in-place, preorder" | Stack-based preorder — pop, link, push right then left |
| Path Sum II | Medium | "find all root-to-leaf paths summing to target" | Iterative DFS with (node, remainingSum, path) on stack |
| Evaluate Division | Medium | "chain ratio queries" | Build graph from equations, BFS/DFS for each query |
| Clone Graph | Medium | "deep copy graph" | Iterative DFS with stack + HashMap original→copy |
Complexity target: O(V + E) for graph problems, O(n) for tree problems. Space O(h) for tree height or O(V) for graphs.
Recognition signal: "without recursion," "iterative traversal," or any recursive problem where the call depth could overflow (very deep trees, large graphs). Also: anything that requires managing "what to process next" explicitly.
Pattern 6: Stack Design Problems
Design a data structure or system that uses a stack internally. These test whether you understand when stacks provide O(1) operations that would otherwise be O(n).
| Problem | Difficulty | Recognition Clue | Key Insight |
|---|---|---|---|
| Min Stack | Medium | "O(1) push, pop, peek, getMin" | Parallel min-stack — track running minimum at each level |
| Max Stack | Hard | "O(1) push, pop, peekMax, popMax" | Two stacks — main + max-tracker; popMax requires lazy deletion |
| LRU Cache | Medium | "O(1) get and put, evict least recently used" | HashMap + doubly linked list (stack not used, but O(1) principle) |
| Implement Stack using Queues | Easy | "mimic LIFO with FIFO" | Two queues: pop rotates n-1 elements; or one queue: push rotates |
| Implement Queue using Stacks | Easy | "mimic FIFO with LIFO" | Input stack + output stack; transfer only when output empty |
| Design Browser History | Medium | "visit, back, forward" | Two stacks — history and forward; clear forward on new visit |
| Design a Stack with Increment Operation | Medium | "increment bottom k elements" | Lazy increment array — mark increment at index k-1, propagate on pop |
| Dinner Plate Stacks | Hard | "push to leftmost non-full, pop from rightmost non-empty" | Array of stacks + heap/set tracking available indices |
Complexity target: O(1) for all operations is usually the target. O(n) worst-case for Max Stack's popMax with lazy deletion.
Recognition signal: "O(1) for all operations," "design a data structure that supports," "implement X using Y." The problem gives you a target complexity that is hard to achieve with naive approaches.
Recommended Study Order
Week 1 — Core LIFO Mechanics Pattern 1 (Basic): Valid Parentheses, Min Stack, Remove Adjacent Duplicates Pattern 4 (Expression): Evaluate RPN, Basic Calculator II, Decode String Week 2 — Monotonic Stack Foundations Pattern 2 (NGE Decreasing): Next Greater Element I & II, Daily Temperatures Pattern 3 (NSE Increasing): Next Smaller Element, Largest Rectangle in Histogram Week 3 — Advanced Problems Pattern 3 (Boundaries): Trapping Rain Water, Maximal Rectangle Pattern 5 (DFS): Binary Tree Traversals (inorder, preorder, postorder) Week 4 — Design and Hard Problems Pattern 6 (Design): Implement Queue using Stacks, Design Browser History Pattern 2 (Hard): 132 Pattern, Sum of Subarray Minimums Pattern 4 (Hard): Basic Calculator, Basic Calculator III Revisit any patterns that felt unclear
Problem-Solving Checklist for Stack Problems
Before writing code, run through this for every stack problem:
1. What must be processed in LIFO order? → What is "opened" and must be "closed"? → What is deferred until the right matching element arrives? 2. Is this a basic stack or a monotonic stack? → "Matching", "nesting", "undo", "pending work" → basic stack → "Next greater/smaller", "span", "nearest boundary" → monotonic stack 3. For monotonic stack: increasing or decreasing? → Looking for next GREATER element → decreasing stack (pop when greater) → Looking for next SMALLER element → increasing stack (pop when smaller) 4. What does the stack store — values or indices? → Need to compute distance or width → store INDICES → Only need the value → store values → When in doubt, store indices (you can always get the value from the index) 5. What is computed at pop time? → Next greater: arr[i] (the element that triggered the pop) → Daily temperatures: i - popped_index → Histogram: height × width (requires left and right boundaries) → Rain water: min(height[left], height[right]) - height[bottom] 6. Is there a sentinel needed? → Largest rectangle needs a 0-height sentinel at the end → Stock span effectively uses -1 as a virtual left boundary → When remaining stack elements after the loop need processing → sentinel 7. Edge cases: → Empty stack before pop or peek → always guard → Single element → does the LIFO property still apply? → All elements decreasing → stack holds all n elements (worst case space) → All elements increasing → stack is always empty after each pop
Pattern Recognition Quick Reference
Use this table when you encounter a new stack problem:
| Signal in Problem | Pattern | Stack Behaviour |
|---|---|---|
| "balanced brackets", "matching pairs" | Basic LIFO | Push openers, pop and match on closers |
| "undo last action", "backspace" | Basic LIFO | Push action, pop to undo |
| "O(1) minimum/maximum" | Stack Design (Min/Max Stack) | Parallel tracking stack |
| "evaluate expression", "postfix", "RPN" | Expression Evaluation | Operand stack, operator stack |
k[string] or repeated expansion | Expression Evaluation | Push (count, prefix), pop on ] |
| "next greater", "warmer", "span" | Monotonic Decreasing | Pop when arr[i] > arr[top] |
| "circular array", "wraps around" | Monotonic (circular) | Traverse 2×, index as i % n |
| "largest area", "rectangle" | Monotonic Increasing | Pop on smaller, compute width |
| "water trapped", "rain" | Monotonic Decreasing | Pop bottom, compute with left/right walls |
| "iterative DFS", "without recursion" | Explicit Stack DFS | Push neighbours, process via stack.pop() |
| "remove k digits", "smallest/largest result" | Monotonic Increasing/Decreasing | Pop greedily to maintain desired order |
| "implement X using Y" | Stack Design | Two-stack transfer pattern |
Difficulty Progression Reference
| Stage | Characteristics | Representative Problems |
|---|---|---|
| Foundation | Single stack, one-pass, push/pop with simple condition | Valid Parentheses, Reverse String, Remove Duplicates |
| Early Intermediate | Min stack auxiliary pattern, basic NGE | Min Stack, Next Greater Element I, Daily Temperatures |
| Intermediate | Circular arrays, multi-stack design, expression evaluation | NGE II, Evaluate RPN, Implement Queue with Stacks |
| Late Intermediate | Two-boundary problems, multi-pass monotonic | Largest Rectangle, Trapping Rain Water, Basic Calculator |
| Advanced | Multi-step combination, hard constraints, lazy structures | 132 Pattern, Sum of Subarray Minimums, Max Stack, Dinner Plate |
Common Interview Topics by Company Focus
Product-based companies (FAANG-tier):
- ›Valid Parentheses is nearly universal — know it cold
- ›Daily Temperatures and Next Greater Element — monotonic stack fundamentals
- ›Trapping Rain Water — both monotonic stack and two-pointer approaches
- ›Largest Rectangle in Histogram — the hardest "must-know" stack problem
- ›Basic Calculator series — tests expression parsing depth
- ›Min Stack — design question asked in almost every top-tier interview
Service-based and on-campus:
- ›Valid Parentheses, Balanced Brackets
- ›Min Stack, Implement Queue using Stacks
- ›Evaluate RPN (postfix evaluation)
- ›Next Greater Element — often the first monotonic stack problem
Startup and mid-size tech:
- ›Decode String — practical string manipulation
- ›Design Browser History — real-world system modelling
- ›Remove Adjacent Duplicates — clean problem with clear stack application
- ›Stock Span — finance domain, clean monotonic stack
Progress Tracking
After solving each problem, record:
- ›Pattern used — which of the 6 patterns does this belong to?
- ›Recognition clue — what phrase in the problem pointed you to the stack?
- ›What the stack stores — values, indices, pairs, or something else?
- ›What is computed at pop time — value, distance, area, or other?
- ›Edge case missed — empty stack? Single element? Circular? Sentinel needed?
- ›Time to solve — target 20-25 minutes for medium problems under interview conditions
After 30 problems across the 6 patterns, you should be able to identify the pattern and the stack type (basic/monotonic increasing/monotonic decreasing) within two minutes of reading any new stack problem.
The decisive signal that pattern recognition is working: when you see a new problem that mentions "next greater" or "span" or "days until," you immediately think "decreasing monotonic stack, store indices, compute at pop time" — before reading the rest of the problem.