Stack
Maintain a stack that is always monotonically increasing or decreasing. When a new element violates the order, pop elements until the invariant is restored. Used for next greater element, largest rectangle, trapping rain water, and stock span.
The motivating example is LeetCode 739, Daily Temperatures, which gives you an array of daily temperatures and asks: for each day, how many days do you have to wait until a warmer temperature? If no future day is warmer, the answer for that day is 0.
Given temperatures = [73, 74, 75, 71, 69, 72, 76, 73], the output is [1, 1, 4, 2, 1, 1, 0, 0]. Day 0 (73 degrees) has to wait 1 day for day 1 (74 degrees). Day 2 (75 degrees) has to wait 4 days for day 6 (76 degrees). Day 6 and day 7 never see a warmer day.
The naive approach is to scan forward from each day until you find a warmer one. For day i, you check day i+1, then i+2, and so on. In the worst case, a strictly decreasing sequence like [100, 99, 98, ..., 1], every day scans all the way to the end without finding a warmer temperature. That is work.
The waste comes from redundancy. If day 5 is warmer than day 4, and day 4 is warmer than day 3, you do not need to independently discover this from each starting point. A monotonic stack lets you resolve multiple days at once, the moment a warmer day arrives.
Maintain a stack of indices whose corresponding temperatures are in decreasing order. As you iterate through the array from left to right, you compare the current temperature against the temperature at the index on top of the stack.
If the current temperature is warmer than the stack top, then you have just found the "next warmer day" for the day at the top of the stack. Pop it, record the distance, and check the new stack top. The current day might also be the answer for that one. Keep popping until the stack is empty or the top has a temperature that is not less than the current one. Then push the current index onto the stack.
The stack maintains a monotone decreasing order of temperatures at all times. Every time a new element breaks that order, it resolves all the pending days that were waiting for something warmer.
Let us trace this step by step. The stack holds indices, and we write the corresponding temperature in parentheses for clarity.
i = 0, temp = 73. Stack is empty. Push 0. Stack: [0(73)].
i = 1, temp = 74. 74 > 73, so day 0 found its answer: 1 - 0 = 1. Pop 0. Stack is empty. Push 1. Stack: [1(74)].
i = 2, temp = 75. 75 > 74, so day 1 found its answer: 2 - 1 = 1. Pop 1. Stack is empty. Push 2. Stack: [2(75)].
i = 3, temp = 71. 71 < 75, no pop. Push 3. Stack: [2(75), 3(71)].
i = 4, temp = 69. 69 < 71, no pop. Push 4. Stack: [2(75), 3(71), 4(69)].
i = 5, temp = 72. 72 > 69, so day 4 found its answer: 5 - 4 = 1. Pop 4. 72 > 71, so day 3 found its answer: 5 - 3 = 2. Pop 3. 72 < 75, stop. Push 5. Stack: [2(75), 5(72)].
i = 6, temp = 76. 76 > 72, so day 5 found its answer: 6 - 5 = 1. Pop 5. 76 > 75, so day 2 found its answer: 6 - 2 = 4. Pop 2. Stack is empty. Push 6. Stack: [6(76)].
i = 7, temp = 73. 73 < 76, no pop. Push 7. Stack: [6(76), 7(73)].
Done. Days 6 and 7 remain on the stack. No warmer day exists for them, so their answer stays 0.
Result: [1, 1, 4, 2, 1, 1, 0, 0].
def dailyTemperatures(temperatures):
n = len(temperatures)
answer = [0] * n
stack = [] # indices, temperatures in decreasing order
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
prev = stack.pop()
answer[prev] = i - prev
stack.append(i)
return answerThe code is short because the monotonic stack pattern is inherently concise. The stack stores indices. For each new temperature, we pop everything that it "resolves," record the gap, then push the current index.
Every index is pushed onto the stack exactly once and popped at most once. The while loop might pop multiple elements on a single iteration, but across the entire run of the for loop, the total number of pops cannot exceed n. So the total work, pushes plus pops, is at most 2n, which is .
This is a common pattern in amortized analysis. The inner loop looks like it could be expensive on any single step, but the "fuel" for each pop was paid for by the earlier push.
Daily Temperatures is a specific instance of the "next greater element" problem. In its purest form, you have an array nums and for each element you want to find the first element to its right that is strictly larger. If none exists, the answer is -1.
def nextGreaterElement(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(n):
while stack and nums[stack[-1]] < nums[i]:
result[stack.pop()] = nums[i]
stack.append(i)
return resultThe only difference from Daily Temperatures is what you record: the value itself instead of the index distance. The monotonic stack structure is identical. You can also flip the comparison to find the "next smaller element" by maintaining an increasing stack instead of a decreasing one.
LeetCode 84, Largest Rectangle in Histogram, is the classic monotonic stack problem and arguably the most important one to master. You are given an array heights where each entry represents the height of a bar with width 1. Find the area of the largest rectangle that can be formed using contiguous bars.
The key insight is that each bar can extend left and right as long as the neighboring bars are at least as tall. The rectangle's height is limited by the shortest bar it spans, and its width is determined by how far that shortest bar can extend in both directions.
A monotonic stack solves this by maintaining a stack of indices in increasing order of height. When you encounter a bar shorter than the one at the top of the stack, you know the top bar cannot extend any further to the right: the current bar is its right boundary. You pop it, and the new stack top tells you where its left boundary is (the last bar shorter than it to the left). The width is the gap between those two boundaries.
i = 0, h = 2. Stack is empty. Push 0. Stack: [0(2)].
i = 1, h = 1. 1 < 2, so bar 0 cannot extend right. Pop 0. Height = 2, width = 1 (stack is empty, so the bar extends all the way to the left, width = i = 1). Area = 2. Push 1. Stack: [1(1)].
i = 2, h = 5. 5 > 1, no pop. Push 2. Stack: [1(1), 2(5)].
i = 3, h = 6. 6 > 5, no pop. Push 3. Stack: [1(1), 2(5), 3(6)].
i = 4, h = 2. 2 < 6, so pop 3. Height = 6, width = 4 - 2 - 1 = 1. Area = 6. Still 2 < 5, so pop 2. Height = 5, width = 4 - 1 - 1 = 2. Area = 10. 2 >= 1, stop. Push 4. Stack: [1(1), 4(2)].
i = 5, h = 3. 3 > 2, no pop. Push 5. Stack: [1(1), 4(2), 5(3)].
Now drain the stack (imagine a sentinel bar of height 0 at position 6).
Pop 5. Height = 3, width = 6 - 4 - 1 = 1. Area = 3.
Pop 4. Height = 2, width = 6 - 1 - 1 = 4. Area = 8.
Pop 1. Height = 1, width = 6 (stack is empty). Area = 6.
The maximum area across all steps is 10, corresponding to the rectangle of height 5 spanning bars at indices 2 and 3.
def largestRectangleArea(heights):
stack = []
max_area = 0
n = len(heights)
for i in range(n + 1):
# Use height 0 as a sentinel to flush the stack at the end
h = heights[i] if i < n else 0
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_areaThe sentinel bar of height 0 at position n ensures every bar is eventually popped from the stack. When computing the width, if the stack is empty after popping, the popped bar was the shortest in the entire histogram, so its width extends from index 0 to index i - 1, a total of i. Otherwise, the width is the gap between the current index and the new stack top, minus one.
The Stock Span problem (LeetCode 901) asks: for each day, how many consecutive days (including today) have had a price less than or equal to today's price? This is essentially a "previous greater element" problem in disguise.
Maintain a decreasing monotonic stack of indices. For each new price, pop all indices whose prices are less than or equal to the current price. The span is the distance from the current index to the new stack top (or the full history if the stack is empty). Then push the current index.
class StockSpanner:
def __init__(self):
self.stack = []
self.day = 0
def next(self, price):
while self.stack and self.stack[-1][1] <= price:
self.stack.pop()
span = self.day - self.stack[-1][0] if self.stack else self.day + 1
self.stack.append((self.day, price))
self.day += 1
return spanEach call to next is amortized because every (day, price) pair is pushed and popped at most once over the lifetime of the object.
Some problems present the array as circular: the element after the last one wraps around to the first. A good example is LeetCode 503, Next Greater Element II.
The standard trick is to iterate from 0 to 2n - 1 and use i % n as the actual index. On the first pass (indices 0 through n-1), you push elements onto the stack. On the second pass (indices n through 2n-1), you continue popping as warmer elements arrive, but you do not push, or equivalently, you push but only record answers for indices less than n.
def nextGreaterElements(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
result[stack.pop()] = nums[i % n]
if i < n:
stack.append(i)
return resultThe double-pass ensures that every element gets a chance to see elements that come before it in the original array. The time complexity remains since each index is pushed at most once and popped at most once.
LeetCode 907 asks: given an array arr, find the sum of min(subarray) for every contiguous subarray. The answer can be enormous, so return it modulo .
The brute force enumerates all subarrays and finds each minimum, but there is a much better approach. Instead of asking "what is the minimum of this subarray?", flip the question: "for each element, how many subarrays is it the minimum of?" If element arr[i] is the minimum of count subarrays, its total contribution to the answer is arr[i] * count.
To compute the count, you need two pieces of information for each index i:
i itself) up to but not including the previous smaller element. This is the distance from i to its "previous less element."i itself) up to but not including the next smaller-or-equal element.The count of subarrays where arr[i] is the minimum is left[i] * right[i]. The asymmetry, strict less on the left, less-or-equal on the right, avoids double-counting when duplicate values exist.
Both left and right are computed with monotonic stacks in a single pass each.
def sumSubarrayMins(arr):
MOD = 10**9 + 7
n = len(arr)
left = [0] * n # distance to previous strictly less element
right = [0] * n # distance to next less-or-equal element
stack = []
# Previous less element (strict <)
for i in range(n):
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
left[i] = i - stack[-1] if stack else i + 1
stack.append(i)
# Next less-or-equal element (<= to handle duplicates)
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[stack[-1]] > arr[i]:
stack.pop()
right[i] = stack[-1] - i if stack else n - i
stack.append(i)
return sum(arr[i] * left[i] * right[i] for i in range(n)) % MODEach element is pushed and popped at most once per stack pass, so the total time is . The same technique applies to Sum of Subarray Maximums by reversing the comparison direction, and to problems like LeetCode 2104 (Sum of Subarray Ranges) which combines both.
Take LeetCode 402: given a string num representing a non-negative integer and an integer k, remove k digits so the remaining number is as small as possible. Return it as a string.
The greedy insight is: scan left to right, and whenever the current digit is smaller than the previous one, removing the previous digit makes the number smaller. A monotonic stack naturally implements this: maintain a stack of digits in non-decreasing order. When a new digit is smaller than the stack top and you still have removals left, pop the stack top (that counts as one removal). After processing all digits, if you still have removals remaining, trim from the end.
'1': Stack empty. Push '1'. Stack: [1]. '4': 4 >= 1, push. Stack: [1, 4]. '3': 3 < 4, pop '4' (k=2). 3 >= 1, push. Stack: [1, 3]. '2': 2 < 3, pop '3' (k=1). 2 >= 1, push. Stack: [1, 2]. '2': 2 >= 2, push. Stack: [1, 2, 2]. '1': 1 < 2, pop '2' (k=0). No more removals. Push '1'. Stack: [1, 2, 1]. '9': k=0, push. Stack: [1, 2, 1, 9].
Result: "1219".
def removeKdigits(num, k):
stack = []
for digit in num:
while k and stack and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
# If k removals remain, trim from the end
if k:
stack = stack[:-k]
return ''.join(stack).lstrip('0') or '0'The same monotonic stack greedy strategy solves LeetCode 316 (Remove Duplicate Letters) and LeetCode 1673 (Find the Most Competitive Subsequence). In 316, instead of a removal budget, you skip characters already in the stack and only pop if the character appears later in the string. In 1673, the removal budget is n - k where k is the target subsequence length. The core loop, popping the stack top when the current element is better and you can still afford to, is identical in all three.
LeetCode 42, Trapping Rain Water, has a well-known two-pointer solution. The monotonic stack approach is an alternative that computes trapped water layer by layer as you scan left to right.
Maintain a stack of indices in decreasing order of height. When you encounter a bar taller than the stack top, the top bar is a "valley": it is bounded on the right by the current bar and on the left by whatever is below it in the stack. Pop the top, compute the water trapped in the horizontal band between the left boundary and the right boundary at the height of the popped bar, and repeat until the stack is empty or the top is no longer shorter than the current bar.
Consider the key moment at i = 3, h = 2. The stack contains [1(1), 2(0)]. Bar 2 (height 0) is shorter than bar 3 (height 2), so pop bar 2. The valley floor is height 0. The left wall is bar 1 (height 1) and the right wall is bar 3 (height 2). The water level is min(1, 2) - 0 = 1, and the width is 3 - 1 - 1 = 1, so we add 1 unit. Now bar 1 (height 1) is still shorter than bar 3 (height 2), so pop bar 1. The stack is empty, so there is no left wall, meaning no more water on this step. Push bar 3. This process repeats across the array, accumulating water layer by layer.
def trap(height):
stack = []
water = 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
valley = height[stack.pop()]
if not stack:
break
left = stack[-1]
bounded_height = min(height[left], h) - valley
width = i - left - 1
water += bounded_height * width
stack.append(i)
return waterEach index is pushed and popped at most once, so the time is and the space is for the stack. The two-pointer approach uses space, but the stack approach is valuable to understand because it generalizes to 2D problems and illustrates how monotonic stacks can compute bounded areas layer by layer.
With LeetCode 853, you are given n cars driving toward a target. Each car has a starting position and a speed. A car that catches up to a slower car ahead forms a "fleet": it cannot pass, so both travel at the slower speed. Return the number of fleets that arrive at the target.
Sort cars by position in decreasing order (closest to target first). Compute each car's time to reach the target: time = (target - position) / speed. Now iterate through these times. If a car's arrival time is greater than that of the car ahead, it cannot catch up, so it forms a new fleet. If its time is less than or equal, it merges into the fleet ahead.
A stack makes this explicit: push a car's time if it is strictly greater than the stack top. Otherwise, it merges into the fleet at the top (skip it). The final stack size is the number of fleets.
def carFleet(target, position, speed):
cars = sorted(zip(position, speed), reverse=True)
stack = []
for pos, spd in cars:
time = (target - pos) / spd
if not stack or time > stack[-1]:
stack.append(time)
return len(stack)The sort is and the stack pass is . The stack maintains a decreasing sequence of arrival times, where each entry represents a distinct fleet. This is a "monotonic stack in spirit" problem: you are keeping a monotone sequence and merging elements that violate the order.
LeetCode 456 asks whether an array contains indices i < j < k such that nums[i] < nums[k] < nums[j], a "1-3-2" pattern where a large element appears between a smaller one on its left and a medium one on its right.
The trick is to scan from right to left, maintaining a stack of candidates for the "3" (the largest element) and tracking the best "2" (the second largest, which the stack has popped). As you move left, any element smaller than the current "2" serves as the "1", completing the pattern.
Specifically, maintain a decreasing stack. When you encounter a value larger than the stack top, pop elements. Each popped element is a potential "2", and you track the maximum popped value as s2. At any point, if the current value is less than s2, return true: the current value is "1", s2 is "2", and the element that caused s2 to be popped was "3".
Scan right to left. s2 = -infinity.
i = 3, val = 2. Stack empty, push 2. Stack: [2].
i = 2, val = 4. 4 > 2, pop 2, set s2 = 2. Push 4. Stack: [4].
i = 1, val = 1. 1 < s2 (2). Found the pattern: 1 < 2 < 4. Return true.
def find132pattern(nums):
stack = []
s2 = float('-inf') # the "2" in 1-3-2
for val in reversed(nums):
if val < s2:
return True
while stack and stack[-1] < val:
s2 = stack.pop()
stack.append(val)
return FalseThe stack is decreasing. Each element is pushed and popped at most once, so the time is . The subtlety is recognizing that scanning right to left and using the stack to find the "3" and "2" simultaneously reduces this to a single-pass monotonic stack problem.
Time: for all the problems above. Each element is pushed onto the stack once and popped at most once, giving at most 2n total stack operations.
Space: in the worst case, when the entire array ends up on the stack (for example, a strictly decreasing sequence in the next-greater-element problem). The result array also takes but that is required output space.
You're probably looking at a monotonic stack when:
Common templates:
Practice Problems (62)