Stack Coding Problems: 60 Questions with Solutions

How stack works, step by step

1. 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.
2. '{' 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.
3. '[' 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.
4. '(' 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.
5. ')' 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.
6. ']' 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.
7. '}' 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.
8. '(' 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.
9. '[' 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.
10. ')' 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 60 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 46 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.

• Valid Parentheses Easy
• Baseball Game Easy
• Remove All Adjacent Duplicates In String Easy

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

• Next Greater Element I Easy
• Evaluate Reverse Polish Notation Medium

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.

• Largest Rectangle in Histogram Hard

Day 8

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

• Longest Valid Parentheses Hard

Next topic: Queue

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 pop b, then a, and push a - b.
• Integer division that must truncate towards zero: Python's // floors, so -7 // 2 is -4; use int(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 (13)

• 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 (39)

• 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 (8)

• 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 46 problems on stack
• Google 32 problems on stack
• Adobe 13 problems on stack
• Meta 9 problems on stack
• Microsoft 7 problems on stack
• Bloomberg 6 problems on stack
• Uber 3 problems on stack
• Flipkart 1 problem on stack
• Ola 1 problem on stack
• Oracle 1 problem on stack
• Zoho 1 problem on stack

Other topics

• Arrays 667 problems
• Strings 282 problems
• Math 213 problems
• Hash Table 202 problems
• Dynamic Programming 195 problems
• Greedy 163 problems
• Sorting 156 problems
• Two Pointers 113 problems
• Matrix 107 problems
• Binary Search 95 problems
• Simulation 88 problems
• Bit Manipulation 83 problems