Stack
The Stack Pattern
A stack holds elements whose fate is still undecided. The monotonic variant keeps its contents in sorted order by popping anything that violates that order as new elements arrive — and each pop is the moment an earlier element gets its answer.
Interactive problems
Free to open
How do you recognise a stack problem?
The problem asks for the next greater or smaller element, needs matching pairs validated (brackets, tags), or involves undoing and revisiting recent state. Histogram and temperature problems are monotonic stack in disguise.
What is the time complexity of the stack pattern?
O(n) time, because every element is pushed once and popped at most once, against O(n²) for scanning forward from each position.
Stack practice problems
Each problem pairs a worked explanation with an interactive visualizer you step through yourself, plus the implementation in JavaScript, Python, Java and C++.
Stack problems by difficulty and complexity
The difficulty, running time and extra space of every stack solution on this page, as each lesson derives them.
| Lesson | Difficulty | Best | Average | Worst | Space |
|---|---|---|---|---|---|
| Stack Overview | Easy | Ω(1) | Θ(1) | O(1) | O(n) |
| Valid Parentheses | Easy | Ω(1) | Θ(n) | O(n) | O(n) |
| Decode String | Medium | Ω(n) | Θ(n + L) | O(n · L) | O(n + L) |
| Longest Valid Parentheses | Hard | Ω(n) | Θ(n) | O(n) | O(n) |
| Overview (Monotonic Stack) | Medium | Ω(n) | Θ(n) | O(n) | O(n) |
| Daily Temperatures | Medium | Ω(n) | Θ(n) | O(n) | O(n) |
| Largest Rectangle in Histogram | Hard | Ω(n) | Θ(n) | O(n) | O(n) |
| Evaluate Reverse Polish Notation | Medium | Ω(n) | Θ(n) | O(n) | O(n) |
| Min Stack | Medium | Ω(1) | Θ(1) | O(1) | O(n) |
Related patterns and concepts
The underlying technique is covered from first principles in the stack lesson in the DSA visualizer curriculum. Stack is one of the 17 coding interview patterns, and its problems also appear in the DSA 75 interview sprint.
Every other coding interview pattern
Depth-First Search · 25 lessons
- Introduction to DFSFree
- DFS FundamentalsFree
- Return Values in DFS
- Invert Binary Tree
- Maximum Depth of Binary Tree
- Path Sum
- Passing Values Down (State)
- Validate Binary Search Tree
- Kth Smallest Element in a BST
- Construct Binary Tree from Preorder and Inorder Traversal
- Binary Tree Tilt
- Diameter of Binary Tree
- Lowest Common Ancestor of a Binary Tree
- Path Sum II
- Longest Univalue Path
- Graphs Overview
- Graph Representation: Adjacency List
- Clone Graph
- Graph Valid Tree
- Matrices as Graphs
- Flood Fill
- Types of DFS (Tree Traversals)
- Number of Islands
- Surrounded Regions
- Pacific Atlantic Water FlowFree