What you will learn
- What a monotonic stack keeps and why it’s O(n).
- Next greater element and daily temperatures.
- Largest rectangle in a histogram, the classic hard version.
Signals
- “Next greater / next smaller / previous greater element”.
- “How many days until…”, “how far can this bar extend?”
- Spans, visibility, or areas bounded by the nearest smaller element.
The idea
Scan left to right and keep a stack of indices still waiting for their answer. When a new value resolves some of them (it’s greater than the values on top), pop and answer them. The remaining stack is always monotonic, which is where the name comes from. Each index is pushed once and popped at most once: O(n).
Code
"""Monotonic stack: next greater element, daily temperatures, largest rectangle."""
def next_greater(nums):
out = [-1] * len(nums)
stack = [] # indices whose next greater element we haven't found yet (values decreasing)
for i, x in enumerate(nums):
while stack and nums[stack[-1]] < x:
out[stack.pop()] = x
stack.append(i)
return out
def daily_temperatures(temps):
out = [0] * len(temps)
stack = []
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
out[j] = i - j
stack.append(i)
return out
def largest_rectangle(heights):
best, stack = 0, [] # indices with increasing heights
for i, h in enumerate(heights + [0]): # trailing 0 flushes the stack
while stack and heights[stack[-1]] >= h:
height = heights[stack.pop()]
left = stack[-1] + 1 if stack else 0
best = max(best, height * (i - left))
stack.append(i)
return best
if __name__ == "__main__":
print(next_greater([2, 1, 2, 4, 3]))
print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
print(largest_rectangle([2, 1, 5, 6, 2, 3]))
Output:
[4, 2, 4, -1, -1]
[1, 1, 4, 2, 1, 1, 0, 0]
10
- Next greater: the stack holds indices with decreasing values. Values left on the stack at the end have no greater element (-1).
- Daily temperatures: same scan, but store the distance
i - j. - Largest rectangle: keep increasing heights. When a lower bar arrives, each popped bar can’t extend further right; its left limit is the new stack top. A trailing 0 flushes the stack at the end. Answer 10 is bars 5 and 6 at height 5.
Increasing or decreasing?
- Looking for the next greater element → keep a decreasing stack (pop smaller values).
- Looking for the next smaller element → keep an increasing stack.
The deque version of this idea solves sliding window maximum.
Practise: monotonic stack problems, and the plain stack section for bracket matching.
Key takeaways
- The stack holds indices still waiting for an answer; new elements resolve them.
- Decreasing stack for next greater, increasing stack for next smaller.
- Each index is pushed and popped once, so O(n).
- Largest rectangle: popping a bar fixes both its right and left limits.
Exercises
- Next greater element in a circular array (loop twice over indices).
- Stock span problem: for each day, how many consecutive previous days had price ≤ today.
- Maximal rectangle in a binary matrix using
largest_rectangleper row.
Quiz
- Which stack order do you keep to find the next greater element?
- Why is the algorithm O(n) despite the inner while loop?
- Why append a 0 to
heightsin largest rectangle?
Show answers
- Decreasing (from bottom to top), popping smaller values when a bigger one arrives.
- Each index is pushed once and popped at most once, so all inner loop iterations add up to at most n.
- A final bar of height 0 is lower than everything, which pops and evaluates every remaining bar.