Monotonic Stack Coding Problems: 45 Questions with Solutions
45 monotonic stack coding problems — 2 easy · 27 medium · 16 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.
- Problems: 45
- By difficulty: 2 easy · 27 medium · 16 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 kept in sorted order — popping every element the new one beats — finds the next greater or next smaller element for every position in one pass. Daily temperatures, the largest rectangle in a histogram and trapping rain water are the classic cases; these problems practise deciding what the stack holds and what each pop means.
New to monotonic stack? Read the Monotonic Stack tutorial first.
How monotonic stack works, step by step
nums = [2, 1, 5, 6, 2, 3]- For each number, find the first larger number to its right. A stack holds the indices still waiting for an answer; their values only decrease from bottom to top, because a larger arrival would already have answered any smaller one below it.
- 2 at index 0 has nothing before it to answer, so index 0 is simply pushed to wait for something larger.
- 1 at index 1 is not larger than 2 on top, so it answers nobody and is pushed to wait too. The waiting values [2, 1] still decrease from bottom to top.
- 5 at index 2 is larger than 1 and 2 on the stack, so 5 is the next greater element for each of them, and they are popped. The stack is now empty, so index 2 is pushed.
- 6 at index 3 is larger than 5 on the stack, so 6 is the next greater element for 5, which is popped. The stack is now empty, so index 3 is pushed.
- 2 at index 4 is not larger than 6 on top, so it answers nobody and is pushed to wait too. The waiting values [6, 2] still decrease from bottom to top.
- 3 at index 5 is larger than 2 on the stack, so 3 is the next greater element for 2, which is popped. 6 is larger than 3, so popping stops there and index 5 is pushed.
- Indices 3 and 5 (values 6 and 3) never met a larger number, so their answer is -1: the result is [5, 5, 6, -1, 3, -1]. Each index was pushed once and popped at most once, so the scan is O(n), not the O(n²) of checking every pair.
Monotonic Stack study plan
12 of the 45 Monotonic Stack problems (2 easy, 7 medium and 3 hard) over 8 days, about 7 h 30 min in all — the pattern first, then easiest to hardest. After that, the other 33 in the full list below are practice at your own pace. Then move on to Monotonic Queue.
Day 1
Learn the pattern: read the essentials and step through the walkthrough above, then solve these 2.
Day 2
Medium problems: the same pattern with one twist each. Name the twist before you code.
- Daily Temperatures Medium
- Next Greater Element II Medium
Day 3
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Remove K Digits Medium
- Car Fleet Medium
Day 4
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
Day 5
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Sum of Subarray Minimums Medium
Day 6
Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.
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.
- Maximal Rectangle Hard
Monotonic Stack: the essentials
When to reach for it
For every element, the nearest greater or smaller element to its left or right: the next warmer day, the next cheaper price, how far each histogram bar can stretch. Also sums over every subarray's minimum or maximum: each element's share is bounded by its nearest smaller (or larger) neighbours. And "remove k digits to make the smallest number", where a digit goes as soon as a smaller one follows.
The pattern
Store indices, not values, so distances and widths are at hand. Scan; while the current element beats the one on top, pop it — the current element is that index's answer. Then push the current index. Indices still on the stack at the end have no answer. Popping smaller values leaves a decreasing stack and finds the next greater; popping larger values finds the next smaller. The plain push-and-pop patterns are on Stack.
def daily_temperatures(t):
ans, stack = [0] * len(t), [] # stack: indices, temperatures falling
for i, x in enumerate(t):
while stack and t[stack[-1]] < x:
j = stack.pop()
ans[j] = i - j # day i is j's next warmer day
stack.append(i)
return ans
Cost
Each index is pushed once and popped at most once, so the nested loop is O(n) overall, with O(n) space.
Common mistakes
<against<=in the pop condition decides how equal values are treated; in subarray-minimum sums, use strict on one side and non-strict on the other, or equal minima are counted twice.- Pushing values when the answer is a distance or a width.
- Forgetting what is left on the stack; in Largest Rectangle in Histogram a final zero-height bar flushes it.
- Circular input: loop over 2n indices using
i % n, pushing only during the first n.
Start with
- Final Prices With a Special Discount in a Shop: the next smaller-or-equal price.
- Daily Temperatures: the next greater, as a distance.
- Largest Rectangle in Histogram: smaller neighbours on both sides.
All monotonic stack problems
Easy (2)
- Nearest Smaller Element Array, Stack
- Final Prices With a Special Discount in a Shop Array, Stack
Medium (27)
- Remove Nodes From Linked List Linked List, Stack, Recursion
- Next Greater Node In Linked List Linked List, Stack, Array
- Construct Binary Search Tree from Preorder Traversal Array, Stack, Tree
- Maximum Binary Tree Array, Divide and Conquer, Stack
- Next Greater Frequency Element Array, Hash Table, Stack
- Beautiful Towers II Array, Stack
- Find the Most Competitive Subsequence Array, Stack, Greedy
- Count Submatrices With All Ones Array, Stack, Matrix
- Maximum Subarray Min-Product Array, Stack, Prefix Sum
- Steps to Make Array Non-decreasing Array, Stack
- Stock Span Problem Array, Stack
- Shortest Subarray to be Removed to Make Array Sorted Array, Two Pointers, Binary Search
- Minimum Number of Increments on Subarrays to Form a Target Array Array, Greedy, Dynamic Programming
- Minimum Cost Tree From Leaf Values Array, Dynamic Programming, Stack
- Buildings With an Ocean View Array, Stack
- The Number of Weak Characters in the Game Array, Greedy, Sorting
- Max Chunks To Make Sorted Array, Stack, Greedy
- Sum of Subarray Ranges Array, Stack
- Maximum Width Ramp Array, Stack, Two Pointers
- 132 Pattern Array, Binary Search, Stack
- Sum of Subarray Minimums Array, Dynamic Programming, Stack
- Remove Duplicate Letters String, Stack, Greedy
- Shortest Unsorted Continuous Subarray Array, Two Pointers, Sorting
- Car Fleet Array, Stack, Sorting
- Remove K Digits String, Stack, Greedy
- Next Greater Element II Array, Stack
- Daily Temperatures Array, Stack
Hard (16)
- Find Maximum Non-decreasing Array Length Array, Binary Search, Dynamic Programming
- Create Maximum Number Array, Greedy, Stack
- Maximum of Minimum for Every Window Size Array, Stack, Sliding Window
- Find the Number of Subarrays Where Boundary Elements Are Maximum Array, Binary Search, Stack
- Max Chunks To Make Sorted II Array, Stack, Greedy
- Sum of Total Strength of Wizards Array, Stack, Prefix Sum
- Maximum Score of a Good Subarray Array, Two Pointers, Stack
- Next Greater Element IV Array, Stack, Sorting
- Maximum Sum Queries Array, Binary Search, Sorting
- Find Building Where Alice and Bob Can Meet Array, Binary Search, Heap (Priority Queue)
- Odd Even Jump Array, Dynamic Programming, Stack
- Smallest K-Length Subsequence With Occurrences of a Letter String, Stack, Greedy
- Apply Operations to Maximize Score Array, Math, Stack
- Maximal Rectangle Array, Matrix, Stack
- Number of Visible People in a Queue Array, Stack
- Largest Rectangle in Histogram Array, Stack
Companies that ask monotonic stack problems
- Amazon 40 problems on monotonic stack
- Google 30 problems on monotonic stack
- Microsoft 12 problems on monotonic stack
- Meta 5 problems on monotonic stack
- Bloomberg 4 problems on monotonic stack
- Flipkart 4 problems on monotonic stack
- Uber 4 problems on monotonic stack
- Adobe 3 problems on monotonic stack
- Sprinklr 3 problems on monotonic stack
- Dream11 2 problems on monotonic stack
- Arcesium 1 problem on monotonic stack
- Capital One 1 problem on monotonic stack
Next topic: Monotonic Queue