Pattern 06 of 22
Monotonic Stack Pattern: Template + 225 LeetCode Problems
Answer "what is the next greater element" for every position in one pass.
- Easy
- 21
- Medium
- 115
- Hard
- 89
- Time
- O(n)
What the monotonic stack pattern is
A monotonic stack is an ordinary stack with one invariant added: its contents are kept increasing or decreasing, and any element that would break the order is popped first. The pops are the algorithm. When a new value evicts the elements below it, that new value is by construction the nearest element to their right that is larger — so "next greater element" for every index falls out of a single left-to-right scan rather than an O(n²) search. The total cost stays linear because each index is pushed once and popped once, no matter how expensive an individual step looks. Pick the direction from the question: a decreasing stack surrenders its top to a larger arrival and answers next-greater queries, an increasing stack answers next-smaller, and storing indices rather than values is almost always right because the distance between them is usually part of the answer.
When to use it
- The question is about the nearest larger or smaller element in some direction.
- You are computing spans, widths or distances between a position and the first position that beats it.
- A histogram, a skyline, temperatures, or stock spans are involved.
- The brute force scans right from every index until it finds something bigger.
The monotonic stack template in Python
The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 225 problems listed below.
def next_greater(nums):
result = [-1] * len(nums)
stack = [] # indices; their values stay decreasing
for i, value in enumerate(nums):
# every index this value evicts has just found its next greater element
while stack and nums[stack[-1]] < value:
result[stack.pop()] = value
stack.append(i)
return resultComplexity characteristics
- Time
- O(n)
- Auxiliary space
- O(n)
Each index is pushed exactly once and popped at most once, so the inner while loop does not multiply the outer loop: the total number of pops over the whole scan is bounded by n even though one step can pop many elements. The stack is the space, and it holds all n indices in the worst case — an input already sorted in the direction the stack maintains never pops anything until the end.
Eyes only
Meet the monotonic stack problem you did not practise.
In the live round, Stealth Interview reads the problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer says. It's a desktop app for macOS and Windows, invisible to screen sharing.
All 225 monotonic stack LeetCode problems
Every problem in the library the monotonic stack pattern applies to, grouped by LeetCode's own difficulty rating. 184 of the 225 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.
Related LeetCode topics
Easy (21)
Medium (115)
Hard (89)
Monotonic Stack pattern FAQ
What is the monotonic stack pattern?
A monotonic stack is an ordinary stack with one invariant added: its contents are kept increasing or decreasing, and any element that would break the order is popped first.
How many LeetCode problems use the monotonic stack pattern?
This page lists 225 LeetCode problems that the monotonic stack pattern applies to: 21 Easy, 115 Medium and 89 Hard. 184 of them carry a complete Python solution with complexity analysis.
What is the time complexity of the monotonic stack pattern?
O(n) time and O(n) space. Each index is pushed exactly once and popped at most once, so the inner while loop does not multiply the outer loop: the total number of pops over the whole scan is bounded by n even though one step can pop many elements. The stack is the space, and it holds all n indices in the worst case — an input already sorted in the direction the stack maintains never pops anything until the end.
When should I use the monotonic stack pattern in an interview?
The question is about the nearest larger or smaller element in some direction. You are computing spans, widths or distances between a position and the first position that beats it.
Which monotonic stack problem should I start with?
LeetCode 35. Search Insert Position is the lowest-numbered Easy problem on this page, which makes it the usual starting point: the technique is visible without the problem's own complications getting in the way.
What patterns are related to monotonic stack?
Stack, Sliding Window, Two Pointers, Greedy. Problems frequently sit in more than one of these, and the overlap is where the interesting follow-up questions come from.
More ways in: all 22 patterns, the curated study lists, or the full problem list.