Monotonic Stack: Next Greater and Smaller Elements
How long until a warmer day?
Daily Temperatures gives you a list of daily temperatures and asks, for each day, how many days you wait for a warmer one. The same question in its plainest form: for each value, what is the first bigger value to its right? That's its next greater element.
The direct way looks ahead from every value until something bigger shows up:
def next_greater(nums):
answer = [-1] * len(nums)
for i in range(len(nums)):
for j in range(i + 1, len(nums)): # look right until something bigger shows up
if nums[j] > nums[i]:
answer[i] = nums[j]
break
return answer
On a falling list, where nothing is ever bigger to the right, every value looks at everything after it: n²/2 comparisons. On our judge:
| Values (falling) | Looking ahead | One pass with a stack |
|---|---|---|
| 2,500 | 234 ms | 0.5 ms |
| 5,000 | 938 ms | 0.9 ms |
| 10,000 | 3,712 ms | 1.7 ms |
Doubling the length made the scan about four times slower.
Here is what the scan misses. A value stops waiting the moment something bigger comes along, and that bigger value is its answer. So the values still waiting can only fall, from the oldest to the newest: if a newer one were bigger, it would already have answered the older one. A new value answers every waiting value it beats, newest first, and those are exactly the ones on top of a stack.
Each pop is an answer
So keep a stack of the indices still waiting, whose values never rise from bottom to top. That's a monotonic stack. For each new value x: while the value on top is smaller than x, x is its next greater element; pop it and write x. Then push x's index to wait its turn. Whatever is left at the end has no next greater element, so it gets −1:
Next greater elements of [2, 1, 2, 4, 3] — The stack holds indices still waiting. Each pop writes an answer below.
vector<int> nextGreater(const vector<int>& nums) {
vector<int> answer(nums.size(), -1); // -1 for a value nothing beats
vector<int> waiting; // indices still waiting; their values never rise
for (int i = 0; i < (int)nums.size(); i++) {
while (!waiting.empty() && nums[waiting.back()] < nums[i]) {
answer[waiting.back()] = nums[i]; // nums[i] is the first bigger value to its right
waiting.pop_back();
}
waiting.push_back(i);
}
return answer;
}
def next_greater(nums):
answer = [-1] * len(nums) # -1 for a value nothing beats
waiting = [] # indices still waiting; their values never rise
for i, x in enumerate(nums):
while waiting and nums[waiting[-1]] < x:
answer[waiting.pop()] = x # x is the first bigger value to its right
waiting.append(i)
return answer
static int[] nextGreater(int[] nums) {
int[] answer = new int[nums.length];
Arrays.fill(answer, -1); // -1 for a value nothing beats
Deque<Integer> waiting = new ArrayDeque<>(); // indices still waiting; their values never rise
for (int i = 0; i < nums.length; i++) {
while (!waiting.isEmpty() && nums[waiting.peek()] < nums[i]) {
answer[waiting.pop()] = nums[i]; // nums[i] is the first bigger value to its right
}
waiting.push(i);
}
return answer;
}
function nextGreater(nums) {
const answer = new Array(nums.length).fill(-1); // -1 for a value nothing beats
const waiting = []; // indices still waiting; their values never rise
for (let i = 0; i < nums.length; i++) {
while (waiting.length && nums[waiting[waiting.length - 1]] < nums[i]) {
answer[waiting.pop()] = nums[i]; // nums[i] is the first bigger value to its right
}
waiting.push(i);
}
return answer;
}
Each printed 4 2 4 -1 -1, 3 4 4 -1, -1 -1 -1 for [2, 1, 2, 4, 3], [1, 3, 2, 4], [5, 4, 3].
Why it's O(n). There's a loop inside a loop, but every index is pushed exactly once and popped at most once, so all the pops together can't outnumber the pushes. We counted on a million random values: 1,000,000 pushes and 999,988 pops, in 595 ms. The stack can hold all n indices when the values only fall, so the space is O(n).
Now you pop or push
Below, you run the stack yourself. At each value you decide: pop the top, because the new value answers it, or push, because the top survives and the new value has to wait too. A wrong call is refused with the comparison that decides it. A counter keeps the pushes and pops, which never pass 2n. Switch modes to try the other three variants.
Four variants: one comparison and when to write
Next smaller is the mirror image: pop while the top is bigger. For the previous greater or smaller value, the answer comes from the left, so it's written when a value arrives, not when it leaves. Pop everything that can never answer anyone again, and whatever is left on top is the answer. Then push.
| Find | Pop while the top is | Write the answer |
|---|---|---|
| next greater | smaller than x | for the popped index: x |
| next smaller | bigger than x | for the popped index: x |
| previous greater | not bigger than x | for x: the top after popping |
| previous smaller | not smaller than x | for x: the top after popping |
Previous Smaller Element asks for the nearest strictly smaller value on the left. The answer is a value, not a distance, so the stack can hold the values themselves:
Previous smaller elements of [4, 5, 2, 10, 8] — Each answer is written when its value arrives, then the value is pushed.
def prev_smaller(arr):
answer, stack = [], [] # stack: values that can still answer someone, rising
for x in arr:
while stack and stack[-1] >= x:
stack.pop() # x is nearer and no bigger: they never answer again
answer.append(stack[-1] if stack else -1) # what's left on top is x's answer
stack.append(x)
return answer
It returned -1 1 1, -1 1 -1 0 3 4, -1 4 -1 2 2 for our three examples, [1, 6, 2], [1, 5, 0, 3, 4, 5], [4, 5, 2, 10, 8].
Distances need indices, circles need two laps
Daily Temperatures wants how far away the warmer day is, not its temperature. A value on the stack can't tell you that; its index can: the wait is i − j, the day of the pop minus the day that waited. This is why the stack holds indices by default:
vector<int> dailyTemperatures(const vector<int>& temps) {
vector<int> wait(temps.size(), 0); // 0 for a day no warmer day follows
vector<int> waiting; // indices of the days still waiting
for (int i = 0; i < (int)temps.size(); i++) {
while (!waiting.empty() && temps[waiting.back()] < temps[i]) {
wait[waiting.back()] = i - waiting.back(); // the index is what gives the distance
waiting.pop_back();
}
waiting.push_back(i);
}
return wait;
}
def daily_temperatures(temps):
wait = [0] * len(temps) # 0 for a day no warmer day follows
waiting = [] # indices of the days still waiting
for i, t in enumerate(temps):
while waiting and temps[waiting[-1]] < t:
j = waiting.pop()
wait[j] = i - j # the index is what gives the distance
waiting.append(i)
return wait
static int[] dailyTemperatures(int[] temps) {
int[] wait = new int[temps.length]; // 0 for a day no warmer day follows
Deque<Integer> waiting = new ArrayDeque<>(); // indices of the days still waiting
for (int i = 0; i < temps.length; i++) {
while (!waiting.isEmpty() && temps[waiting.peek()] < temps[i]) {
int j = waiting.pop();
wait[j] = i - j; // the index is what gives the distance
}
waiting.push(i);
}
return wait;
}
function dailyTemperatures(temps) {
const wait = new Array(temps.length).fill(0); // 0 for a day no warmer day follows
const waiting = []; // indices of the days still waiting
for (let i = 0; i < temps.length; i++) {
while (waiting.length && temps[waiting[waiting.length - 1]] < temps[i]) {
const j = waiting.pop();
wait[j] = i - j; // the index is what gives the distance
}
waiting.push(i);
}
return wait;
}
Each printed 1 1 4 2 1 1 0 0, 1 1 1 0, 1 1 0 for LeetCode's three examples. Days nothing warmer follows keep their 0.
Next Greater Element II puts the array on a circle: after the last value comes the first again. The last value's answer may be near the start, so walk the array twice, reading index k mod n. Push only in the first lap; the second lap only answers what's still waiting:
Next greater on the circle [1, 2, 1] — Two laps over the same three values; the second lap only pops.
vector<int> nextGreaterCircular(const vector<int>& nums) {
int n = nums.size();
vector<int> answer(n, -1);
vector<int> waiting;
for (int k = 0; k < 2 * n; k++) { // two laps: the second answers what the first left waiting
int x = nums[k % n];
while (!waiting.empty() && nums[waiting.back()] < x) {
answer[waiting.back()] = x;
waiting.pop_back();
}
if (k < n) waiting.push_back(k); // each index waits once, pushed in the first lap
}
return answer;
}
def next_greater_circular(nums):
n = len(nums)
answer = [-1] * n
waiting = []
for k in range(2 * n): # two laps: the second answers what the first left waiting
x = nums[k % n]
while waiting and nums[waiting[-1]] < x:
answer[waiting.pop()] = x
if k < n:
waiting.append(k) # each index waits once, pushed in the first lap
return answer
static int[] nextGreaterCircular(int[] nums) {
int n = nums.length;
int[] answer = new int[n];
Arrays.fill(answer, -1);
Deque<Integer> waiting = new ArrayDeque<>();
for (int k = 0; k < 2 * n; k++) { // two laps: the second answers what the first left waiting
int x = nums[k % n];
while (!waiting.isEmpty() && nums[waiting.peek()] < x) {
answer[waiting.pop()] = x;
}
if (k < n) waiting.push(k); // each index waits once, pushed in the first lap
}
return answer;
}
function nextGreaterCircular(nums) {
const n = nums.length;
const answer = new Array(n).fill(-1);
const waiting = [];
for (let k = 0; k < 2 * n; k++) { // two laps: the second answers what the first left waiting
const x = nums[k % n];
while (waiting.length && nums[waiting[waiting.length - 1]] < x) {
answer[waiting.pop()] = x;
}
if (k < n) waiting.push(k); // each index waits once, pushed in the first lap
}
return answer;
}
Each printed 2 -1 2, 2 3 4 -1 4 for [1, 2, 1], [1, 2, 3, 4, 3]. Still O(n): 2n reads, n pushes, at most n pops.
The same stack in three more problems
Online Stock Span reports, for each day's price, how many days in a row up to today the price was no higher. Keep (price, span) pairs: a new price swallows every lower or equal day on top, together with the days those had already swallowed:
class StockSpanner:
def __init__(self):
self.stack = [] # (price, span): each covers the days it swallowed
def next(self, price):
span = 1
while self.stack and self.stack[-1][0] <= price:
span += self.stack.pop()[1] # a day no higher, and everything it covered, joins this span
self.stack.append((price, span))
return span
It returned 1 1 1 2 1 4 6 for LeetCode's prices 100, 80, 60, 70, 60, 75, 85.
Car Fleet has cars driving to a target at different speeds; a faster car that catches a slower one slows down and they continue as one fleet. Go from the car nearest the target backwards and work out when each would arrive alone. A car arriving no later than the fleet ahead catches it; one arriving later starts a new fleet. The stack holds the fleets' arrival times, rising:
def car_fleet(target, position, speed):
times = [] # arrival time of each fleet ahead
for p, s in sorted(zip(position, speed), reverse=True): # from the car nearest the target back
t = (target - p) / s
if not times or t > times[-1]:
times.append(t) # it can't catch the fleet ahead: a new fleet
return len(times)
It returned 3, 1 and 1 for LeetCode's three examples.
Remove K Digits removes k digits from a number to make it as small as possible. A digit followed by a smaller one should go first, so keep a stack of digits that never falls, popping a bigger digit while removals remain. If removals are left at the end, the digits only rise, so cut from the end:
def remove_k_digits(num, k):
stack = [] # the digits kept so far, never falling
for d in num:
while k and stack and stack[-1] > d:
stack.pop() # a bigger digit before a smaller one: removing it helps most
k -= 1
stack.append(d)
if k:
stack = stack[:-k] # still rising: the last digits are the biggest
return "".join(stack).lstrip("0") or "0"
It returned 1219, 200, 0 and 11 for 1432219 with k = 3, 10200 with 1, 10 with 2 and 112 with 1.
Spotting it, and when it breaks
The clues. For each element, the nearest bigger or smaller one, to the left or the right; "how many days until", "how far back", "the first element that"; anything where a value stops mattering once something bigger (or smaller) comes after it. The next lesson, Monotonic Stack: Subarray Minimums and Histograms, uses both boundaries at once.
The near-misses. The largest value in every window of size k needs elements to leave from the old end too: that's a monotonic deque (Sliding Window Maximum, in Queues & Deques). The k-th greater element, or the greatest value in an arbitrary range, needs a heap or a segment tree.
When it breaks. When the question isn't "nearest": the stack throws away values the moment they're beaten, so it can't answer "the second bigger" or "the biggest after i".
Bugs that cost a submission
<= where duplicates need <.
def next_greater(nums):
answer = [-1] * len(nums) # -1 for a value nothing beats
waiting = [] # indices still waiting; their values never rise
for i, x in enumerate(nums):
while waiting and nums[waiting[-1]] <= x: # pops an equal value too
answer[waiting.pop()] = x # x is the first bigger value to its right
waiting.append(i)
return answer
On [2, 2, 3] it returned 2 3 -1: the second 2 popped the first and became its "greater" element. The answer is 3 3 -1.
Values instead of indices. Keying the answers by value works only while the values are distinct:
def next_greater(nums):
answer, stack = {}, [] # the stack holds values; answers go in a dict keyed by value
for x in nums:
while stack and stack[-1] < x:
answer[stack.pop()] = x
stack.append(x)
return [answer.get(x, -1) for x in nums]
On [1, 3, 1, 2] it returned 2 -1 2 -1: the second 1 overwrote the first one's answer. With indices the answer is 3 -1 2 -1.
One lap on a circle.
def next_greater_circular(nums):
n = len(nums)
answer = [-1] * n
waiting = []
for k in range(n): # one lap only
x = nums[k % n]
while waiting and nums[waiting[-1]] < x:
answer[waiting.pop()] = x
if k < n:
waiting.append(k) # each index waits once, pushed in the first lap
return answer
On [1, 2, 1] it returned 2 -1 -1: the last 1 never saw the 2 at the start. Two laps give 2 -1 2.
Removals left over. When the digits only rise, nothing gets popped:
def remove_k_digits(num, k):
stack = [] # the digits kept so far, never falling
for d in num:
while k and stack and stack[-1] > d:
stack.pop() # a bigger digit before a smaller one: removing it helps most
k -= 1
stack.append(d)
return "".join(stack).lstrip("0") or "0"
It returned 12345 for 12345 with k = 2 and 112 for 112 with k = 1, removing nothing. Cutting k digits from the end gives 123 and 11.
Check yourself
Quiz
1 / 6Multiple choice
Multiple choice
Multiple choice
[2, 2, 3], what does next greater return if the loop pops while the top is <= x?Multiple choice
Multiple choice
Multiple choice
Practice problems
From easier to harder:
- Next Greater Element I: the template, answered through a map from value to answer.
- Previous Smaller Element: written on arrival.
- Daily Temperatures: distances, so indices.
- Online Stock Span: spans swallowed with each pop.
- Next Greater Element II: two laps.
- Car Fleet: arrival times, from the target back.
- Remove K Digits: a rising stack of digits, then trim.
Next, Monotonic Stack: Subarray Minimums and Histograms: both boundaries of each element at once.