A family of interview problems asks the same question in different clothes: for each element, what’s the nearest element to its right (or left) that is bigger (or smaller)? How many days until a warmer temperature? Which bar stops this rectangle from extending? How far back does today’s stock price dominate? The brute-force answer scans outward from every element, which is O(n²). A monotonic stack answers all of them in a single pass.
The name comes from the invariant: the values on the stack, read from bottom to top, are always sorted (monotonic). But the more useful way to think about it is as a waiting room.
The stack is a waiting room
Take Daily Temperatures: given daily temperatures, return for each day how many days you’d wait for a warmer one, or 0 if none comes. For [73, 74, 75, 71, 69, 72, 76, 73] the answer is [1, 1, 4, 2, 1, 1, 0, 0].
Scan left to right. Every day starts out “waiting” for a warmer day. When a new day arrives, it can resolve some of the waiting days: any waiting day colder than today has found its answer. Those leave the waiting room. Then today joins it.
The key observation is which waiting days today can resolve. If day A is waiting and a later, colder day B is also waiting, B sits on top of A. Today can’t be warmer than A without also being warmer than B. So the days that today resolves are always at the top of the stack, and you can stop at the first one that’s at least as warm as today. That’s why a stack fits, and why its contents stay in decreasing order of temperature from bottom to top.
def daily_temperatures(temps):
answer = [0] * len(temps)
stack = [] # indices still waiting for a warmer day
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t: # today resolves every colder day on top
j = stack.pop()
answer[j] = i - j
stack.append(i)
return answerWith a print after each day, showing the temperatures of the waiting days:
day 0 (73): stack temps=[73] answer=[0, 0, 0, 0, 0, 0, 0, 0]
day 1 (74): stack temps=[74] answer=[1, 0, 0, 0, 0, 0, 0, 0]
day 2 (75): stack temps=[75] answer=[1, 1, 0, 0, 0, 0, 0, 0]
day 3 (71): stack temps=[75, 71] answer=[1, 1, 0, 0, 0, 0, 0, 0]
day 4 (69): stack temps=[75, 71, 69] answer=[1, 1, 0, 0, 0, 0, 0, 0]
day 5 (72): stack temps=[75, 72] answer=[1, 1, 0, 2, 1, 0, 0, 0]
day 6 (76): stack temps=[76] answer=[1, 1, 4, 2, 1, 1, 0, 0]
day 7 (73): stack temps=[76, 73] answer=[1, 1, 4, 2, 1, 1, 0, 0]
[1, 1, 4, 2, 1, 1, 0, 0]Day 5 (72) is the interesting step. It pops 69 (day 4, waited 1 day) and 71 (day 3, waited 2 days), then stops at 75 because 72 isn’t warmer, and joins the room. Day 6 (76) clears everything, including day 2, which waited 4 days. Days 6 and 7 are still waiting when the input ends, so their answers stay 0. Whatever is left on the stack at the end has no answer, and the default value handles it.
Why a loop inside a loop is still linear
The while inside the for makes this look quadratic, and an interviewer may ask you to justify O(n). The argument is about total work, not work per iteration. Every index is pushed exactly once. An index can only be popped after it’s been pushed, and once popped it never returns. So across the entire run there are at most n pops, no matter how they’re distributed among iterations. A single day might pop a thousand entries, but then those thousand entries can never cost anything again.
Counting the operations on 100,000 random temperatures confirms it:
n=100,000: pushes=100,000 pops=98,637 total stack operations=198,637Under 2n. This is the same amortized reasoning as a dynamic array’s resizing: an expensive step is paid for by many cheap ones before it. Time is O(n), and space is O(n) in the worst case, a strictly decreasing input where nothing is ever popped.
Strict or not: what duplicates do
The comparison in the while decides what “greater” means, and duplicates expose the difference:
def next_greater(nums, strict=True):
res = [-1] * len(nums)
stack = []
for i, x in enumerate(nums):
while stack and (nums[stack[-1]] < x if strict else nums[stack[-1]] <= x):
res[stack.pop()] = x
stack.append(i)
return resnext greater: [3, 3, -1, -1]
next greater-or-equal: [2, 3, -1, -1]For [2, 2, 3, 1], the strict version leaves the first 2 waiting when the second 2 arrives, so both are resolved by 3. The non-strict version lets the second 2 resolve the first. Neither is wrong; the problem statement decides. Reading “warmer” as strictly greater is why Daily Temperatures uses <. When a problem counts things on both sides of an element (like summing subarray minimums), you typically need strict on one side and non-strict on the other, or equal values get counted twice.
Picking the variant
There are four combinations of direction and comparison, and they map neatly onto stack order:
- Next greater to the right: scan left to right, pop while the top is smaller. The stack is decreasing.
- Next smaller to the right: scan left to right, pop while the top is larger. The stack is increasing.
- Previous greater or smaller to the left: either scan right to left with the same rules, or scan left to right and read the answer from whatever is on top of the stack after popping, just before you push.
That last trick is worth remembering, because it gives you both neighbours in one pass: when an index is popped, the element doing the popping is its next smaller (or greater), and the element left underneath it is its previous one.
Always push indices rather than values. Daily Temperatures needs the distance i - j, and histogram problems need widths. With an index, you can get the value with temps[j]; with a value, the position is gone.
Both neighbours at once: largest rectangle in a histogram
Largest Rectangle in Histogram is the problem where that “both neighbours” trick pays off. Given bar heights, find the largest rectangle that fits under the bars. For any bar, the widest rectangle using its full height extends left until a shorter bar and right until a shorter bar. So you need the previous smaller and next smaller for every bar, which an increasing stack gives you at pop time:
def largest_rectangle(heights):
stack = [] # indices of bars with increasing heights
best = 0
for i, h in enumerate(heights + [0]): # the 0 sentinel flushes the stack at the end
while stack and heights[stack[-1]] >= h:
top = stack.pop()
height = heights[top]
left = stack[-1] if stack else -1 # previous smaller bar (or the wall)
width = i - left - 1 # i is the next smaller bar
best = max(best, height * width)
stack.append(i)
return best10 4 9 0Those are [2, 1, 5, 6, 2, 3], [2, 4], [3, 3, 3] and []. In the first, the bar of height 5 is popped when the 2 at index 4 arrives; the bar underneath it on the stack is the 1 at index 1, so the rectangle spans indices 2 to 3, width 2, area 10. The appended 0 is a sentinel: it’s shorter than every bar, so it forces everything still on the stack to be popped and measured at the end, without a separate cleanup loop. Here the comparison is >=, so among equal heights the earlier bar gets popped with a too-narrow width, but the last bar of the run is measured with the full width, so the maximum is still right (the [3, 3, 3] case returns 9).
Interview practice: next greater in a circular array
Given a circular array (the element after the last one is the first), return the next greater element for each position, or -1 if there isn’t one. For [1, 2, 1] the answer is [2, -1, 2]: the last 1 wraps around to find the 2. Solve it in O(n).
Answer
Run the usual next-greater scan, but walk the array twice, using i % n to wrap. The first pass handles everything that has a greater element to its right; the second pass gives elements still waiting a chance to be resolved by elements before them. Push indices only during the first pass, since second-pass positions are duplicates of indices already handled.
def next_greater_circular(nums):
n = len(nums)
res = [-1] * n
stack = []
for i in range(2 * n): # walk the array twice
x = nums[i % n]
while stack and nums[stack[-1]] < x:
res[stack.pop()] = x
if i < n: # only first-pass indices need answers
stack.append(i)
return res
print(next_greater_circular([1, 2, 1]), next_greater_circular([1, 2, 3, 4, 3]),
next_greater_circular([5, 5, 5]), next_greater_circular([3, 8, 4, 1, 2]))[2, -1, 2] [2, 3, 4, -1, 4] [-1, -1, -1] [8, -1, 8, 2, 3]
3,000 random arrays: matches the O(n^2) brute forceThe second line is from a randomised comparison against a brute-force scan that checks every other position in circular order. Two laps are enough: any element’s next greater, if it exists, is fewer than n steps away. Each index is still pushed once and popped at most once, so time is O(n) and space O(n). The maximum value (and any copies of it, as in [5, 5, 5]) never gets popped and correctly stays -1. A follow-up worth preparing: Trapping Rain Water can be solved with a monotonic stack too, though the two-pointer version uses less memory.