Stack Coding Problems: 111 Questions with Solutions
111 stack coding problems — 22 easy · 64 medium · 25 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.
- Problems: 111
- By difficulty: 22 easy · 64 medium · 25 hard
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
- Cost: Free on every plan; sign in to run and submit
A stack remembers things in the order they can be undone: the last item pushed is the first one back. Matching brackets, evaluating expressions, simplifying a path, finding the next greater element and undoing a sequence of operations all fall out of one push-and-pop loop. The problems here practise seeing the stack in a question that never mentions one.
New to stack? Read the Stack Data Structure tutorial first.
How stack works, step by step
s = "{[()]}([)]"- A closing bracket must close the most recent opener that is still open: last in, first out, which is exactly a stack. Read the string left to right, push every opener, and on a closer check that the top of the stack is its partner.
- '{' at index 0 is an opener, so it is pushed. It waits on the stack until its partner arrives with nothing still open above it.
- '[' at index 1 is an opener, so it is pushed on top of '{'. Whatever is on top must be closed first, so '[' now has to be closed before '{' can be.
- '(' at index 2 is an opener, so it is pushed on top of '['. Whatever is on top must be closed first, so '(' now has to be closed before '[' can be.
- ')' at index 3 needs '(', and the top of the stack is '(', so they match and '(' is popped. '[' is on top again, the next opener waiting to be closed.
- ']' at index 4 needs '[', and the top of the stack is '[', so they match and '[' is popped. '{' is on top again, the next opener waiting to be closed.
- '}' at index 5 needs '{', and the top of the stack is '{', so they match and '{' is popped. The stack is empty, so "{[()]}" is balanced on its own.
- '(' at index 6 is an opener, so it is pushed. It waits on the stack until its partner arrives with nothing still open above it.
- '[' at index 7 is an opener, so it is pushed on top of '('. Whatever is on top must be closed first, so '[' now has to be closed before '(' can be.
- ')' at index 8 needs '(', but the top is '[': the pairs cross, so the string is invalid and the scan stops. Counting brackets would miss this. One pass, each character pushed and popped at most once: O(n) time and O(n) space.
Stack study plan
14 of the 111 Stack problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 97 in the full list below are practice at your own pace. Then move on to Queue.
Day 1
Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.
Day 2
Medium problems: the same pattern with one twist each. Name the twist before you code.
Day 3
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Daily Temperatures Medium
- Decode String Medium
Day 4
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Next Greater Element II Medium
- Remove K Digits Medium
Day 5
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Simplify Path Medium
- Asteroid Collision Medium
Day 6
Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.
- Trapping Rain Water Hard
Day 7
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Day 8
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Stack: the essentials
When to reach for it
Nested structure — brackets, tags, encodings like 3[a2[c]]; a symbol that cancels the most recent unmatched one (a backspace, a closing bracket, two colliding asteroids); an expression to evaluate; a recursion you want to run as a loop. The test is whether the item you need next is always the most recent one not yet dealt with.
The pattern
Scan left to right. Push whatever is waiting for a partner; when the current element resolves the top, pop and combine. Whatever is left at the end is unmatched. In reverse Polish notation, numbers are pushed and each operator pops two operands and pushes the result. When the stack must stay in sorted order to answer "next greater" questions, it is a Monotonic Stack.
def is_valid(s):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
else:
stack.append(ch)
return not stack
Cost
Each element is pushed and popped at most once: O(n) time and, in the worst case (all openers), O(n) space.
Common mistakes
- Popping or peeking an empty stack; check before every pop.
- Declaring success after the scan without checking that the stack is empty.
- Operand order for
-and/: the first pop is the right-hand operand, so popb, thena, and pusha - b. - Integer division that must truncate towards zero: Python's
//floors, so-7 // 2is-4; useint(a / b).
Start with
- Valid Parentheses: push openers, pop on closers.
- Evaluate Reverse Polish Notation: a stack of operands.
- Decode String: a stack of partial strings for nested repeats.
All stack problems
Easy (22)
- Implement Queue using Stacks Queue, Design
- Implement Stack using Queues Queue, Design
- Palindrome Linked List Linked List, Two Pointers, Recursion
- Kth Largest Element in BST Tree, Depth-First Search
- Increasing Order Search Tree Tree, Depth-First Search
- Binary Tree Postorder Traversal Tree, Depth-First Search
- Binary Tree Preorder Traversal Tree, Depth-First Search
- Binary Tree Inorder Traversal Tree, Depth-First Search
- Nearest Smaller Element Array, Monotonic Stack
- Minimum String Length After Removing Substrings String, Simulation
- Number of Students Unable to Eat Lunch Array, Queue, Simulation
- Final Prices With a Special Discount in a Shop Array, Monotonic Stack
- Crawler Log Folder Array, String
- Make The String Great String
- Baseball Game Array, String, Simulation
- Reverse Prefix of Word Two Pointers, String
- Remove Outermost Parentheses String
- Maximum Nesting Depth of the Parentheses String
- Remove All Adjacent Duplicates In String String
- Next Greater Element I Array, Hash Table
- Backspace String Compare String, Two Pointers
- Valid Parentheses String
Medium (64)
- Design Browser History Array, Linked List, Design
- Design a Stack With Increment Operation Array, Design
- Min Stack Design
- Double a Number Represented as a Linked List Linked List, Math
- Remove Nodes From Linked List Linked List, Monotonic Stack, Recursion
- Maximum Twin Sum of a Linked List Linked List, Two Pointers
- Next Greater Node In Linked List Linked List, Monotonic Stack, Array
- Add Two Numbers II Linked List, Math
- Reorder List Linked List, Two Pointers, Recursion
- Construct Binary Search Tree from Preorder Traversal Array, Tree, Binary Search
- Maximum Binary Tree Array, Divide and Conquer, Tree
- Flatten Binary Tree to Linked List Tree, Depth-First Search
- Infix to Postfix String
- Next Greater Frequency Element Array, Hash Table, Monotonic Stack
- The Celebrity Problem Array, Two Pointers, Graph
- Check if a Parentheses String Can Be Valid String, Greedy
- Beautiful Towers II Array, Monotonic Stack
- Find the Most Competitive Subsequence Array, Greedy, Monotonic Stack
- Count Submatrices With All Ones Array, Matrix, Monotonic Stack
- Maximum Subarray Min-Product Array, Monotonic Stack, Prefix Sum
- Steps to Make Array Non-decreasing Array, Monotonic Stack
- Exclusive Time of Functions Array
- Stock Span Problem Array, Monotonic Stack
- Using a Robot to Print the Lexicographically Smallest String Hash Table, String, Greedy
- Construct Smallest Number From DI String String, Greedy, Backtracking
- Minimum Number of Increments on Subarrays to Form a Target Array Array, Greedy, Dynamic Programming
- Minimum Deletions to Make String Balanced String, Dynamic Programming
- Lexicographically Minimum String After Removing Stars String, Greedy, Heap (Priority Queue)
- Minimum Cost Tree From Leaf Values Array, Dynamic Programming, Monotonic Stack
- Minimum Additions to Make Valid String String, Greedy, Dynamic Programming
- Count Collisions on a Road String, Simulation, Greedy
- Clumsy Factorial Math, Simulation
- Longest Well-Performing Interval Array, Hash Table, Prefix Sum
- Buildings With an Ocean View Array, Monotonic Stack
- Minimum Insertions to Balance a Parentheses String String, Greedy
- Remove All Adjacent Duplicates in String II String
- The Number of Weak Characters in the Game Array, Greedy, Sorting
- Maximum Score From Removing Substrings String, Greedy
- Minimum Number of Swaps to Make the String Balanced String, Greedy, Two Pointers
- Remove All Occurrences of a Substring String, Simulation
- Max Chunks To Make Sorted Array, Greedy, Monotonic Stack
- Sum of Subarray Ranges Array, Monotonic Stack
- Removing Stars From a String String, Simulation
- Reverse Substrings Between Each Pair of Parentheses String
- Basic Calculator II Math, String
- Validate Stack Sequences Array, Simulation
- Maximum Width Ramp Array, Monotonic Stack, Two Pointers
- 132 Pattern Array, Binary Search, Monotonic Stack
- Sum of Subarray Minimums Array, Dynamic Programming, Monotonic Stack
- Build an Array With Stack Operations Array, Simulation
- Check If Word Is Valid After Substitutions String
- Score of Parentheses String
- Minimum Remove to Make Valid Parentheses String
- Minimum Add to Make Parentheses Valid String, Greedy
- Remove Duplicate Letters String, Greedy, Monotonic Stack
- Valid Parenthesis String String, Dynamic Programming, Greedy
- Car Fleet Array, Sorting, Monotonic Stack
- Asteroid Collision Array, Simulation
- Decode String String, Recursion
- Simplify Path String
- Remove K Digits String, Greedy, Monotonic Stack
- Next Greater Element II Array, Monotonic Stack
- Daily Temperatures Array, Monotonic Stack
- Evaluate Reverse Polish Notation Array, Math
Hard (25)
- Dinner Plate Stacks Hash Table, Heap (Priority Queue), Design
- Recover a Tree From Preorder Traversal Tree, Depth-First Search, String
- Minimum Number of Visited Cells in a Grid Array, Dynamic Programming, Breadth-First Search
- Find Maximum Non-decreasing Array Length Array, Binary Search, Dynamic Programming
- Create Maximum Number Array, Greedy, Monotonic Stack
- Brace Expansion II String, Backtracking, Breadth-First Search
- Number of Atoms Hash Table, String, Sorting
- Basic Calculator Math, String, Recursion
- Maximum of Minimum for Every Window Size Array, Monotonic Stack, Sliding Window
- Find the Number of Subarrays Where Boundary Elements Are Maximum Array, Binary Search, Monotonic Stack
- Robot Collisions Array, Sorting, Simulation
- Max Chunks To Make Sorted II Array, Greedy, Monotonic Stack
- Replace Non-Coprime Numbers in Array Array, Math, Number Theory
- Sum of Total Strength of Wizards Array, Monotonic Stack, Prefix Sum
- Maximum Score of a Good Subarray Array, Two Pointers, Monotonic Stack
- Next Greater Element IV Array, Monotonic Stack, Sorting
- Parsing A Boolean Expression String, Recursion
- Odd Even Jump Array, Dynamic Programming, Monotonic Stack
- Smallest K-Length Subsequence With Occurrences of a Letter String, Greedy, Monotonic Stack
- Apply Operations to Maximize Score Array, Math, Greedy
- Maximal Rectangle Array, Matrix, Dynamic Programming
- Number of Visible People in a Queue Array, Monotonic Stack
- Longest Valid Parentheses String, Dynamic Programming
- Largest Rectangle in Histogram Array, Monotonic Stack
- Trapping Rain Water Array, Two Pointers, Dynamic Programming
Companies that ask stack problems
- Amazon 97 problems on stack
- Google 63 problems on stack
- Microsoft 33 problems on stack
- Meta 17 problems on stack
- Adobe 15 problems on stack
- Bloomberg 12 problems on stack
- Uber 7 problems on stack
- Flipkart 6 problems on stack
- Sprinklr 6 problems on stack
- PhonePe 4 problems on stack
- Airbnb 3 problems on stack
- Apple 3 problems on stack
Next topic: Queue