12.04Beginner / Intermediate5 topics20 min5 interactive animations

Monotonic stacks

A monotonic stack keeps its elements in sorted order, popping those that can no longer be an answer. It solves next greater and smaller element, previous greater and smaller element, the stock span, daily temperatures and the largest rectangle in a histogram in O(n).

Learning goals

Maintain a monotonic stack of indexes
Solve next and previous greater or smaller queries
Apply the pattern to spans, temperatures and histograms
Argue why each element is pushed and popped once

Prerequisites

ImplementationsFoundational problem-solving patterns

12.04.1

Next greater/smaller

For each element find the first element to its right that is greater (or smaller). Scan left to right with a stack of indexes whose answers are still unknown, kept in decreasing order of value: when the current value is greater than the top, the current value is the top's answer, so pop and record it, and repeat. Each index is pushed once and popped once, so the whole scan is O(n), even though one step may pop many.

Run next greater on your own array and watch indexes leave the stack when their answer arrives.

Java

1static int[] nextGreater(int[] a) {
2    int[] ans = new int[a.length]; Arrays.fill(ans, -1);
3    Deque<Integer> stack = new ArrayDeque<>();               // indexes waiting for a greater value
4    for (int i = 0; i < a.length; i++) {
5        while (!stack.isEmpty() && a[stack.peek()] < a[i]) ans[stack.pop()] = a[i];
6        stack.push(i);
7    }
8    return ans;
9}

Next greater element (monotonic stack)

Interactive · edit the input

int[] arr · length 8

01234567

CurrentOn the stackAnswered

stack (bottom→top)

empty

result[]

·0

·1

·2

·3

·4

·5

·6

·7

Setup

The stack holds indices whose values decrease from bottom to top. Each index is pushed once and popped at most once, so the whole scan is O(n).

Step 1 / 27

Java

1public static int[] nextGreater(int[] arr) {
2    int n = arr.length;
3    int[] result = new int[n];
4    Arrays.fill(result, -1);
5    Deque<Integer> stack = new ArrayDeque<>();      // indices; their values decrease bottom to top
6    for (int i = 0; i < n; i++) {
7        while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
8            result[stack.pop()] = arr[i];          // arr[i] answers the popped index
9        }
10        stack.push(i);
11    }
12    return result;
13}

Live state

0 pushes0 pops

No condition evaluated on this step

Execution trace (dry run table)Show 27 steps

Step	Line	State	What happens
1	L5	n=8	The stack holds indices whose values decrease from bottom to top. Each index is pushed once and popped at most once, so the whole scan is O(n).
2	L10	i=0	Push index 0.
3	L7	i=1 arr[i]=7 top=0	7 is the first greater value to the right of index 0.
4	L8	i=1 popped=0	result[0] = 7.
5	L10	i=1	Push index 1.
6	L7	i=2 arr[i]=3 top=1	The stack top survives, so stop popping.
7	L10	i=2	Push index 2.
8	L7	i=3 arr[i]=5 top=2	5 is the first greater value to the right of index 2.
9	L8	i=3 popped=2	result[2] = 5.
10	L7	i=3 arr[i]=5 top=1	The stack top survives, so stop popping.
11	L10	i=3	Push index 3.
12	L7	i=4 arr[i]=9 top=3	9 is the first greater value to the right of index 3.
13	L8	i=4 popped=3	result[3] = 9.
14	L7	i=4 arr[i]=9 top=1	9 is the first greater value to the right of index 1.
15	L8	i=4 popped=1	result[1] = 9.
16	L10	i=4	Push index 4.
17	L7	i=5 arr[i]=2 top=4	The stack top survives, so stop popping.
18	L10	i=5	Push index 5.
19	L7	i=6 arr[i]=6 top=5	6 is the first greater value to the right of index 5.
20	L8	i=6 popped=5	result[5] = 6.
21	L7	i=6 arr[i]=6 top=4	The stack top survives, so stop popping.
22	L10	i=6	Push index 6.
23	L7	i=7 arr[i]=8 top=6	8 is the first greater value to the right of index 6.
24	L8	i=7 popped=6	result[6] = 8.
25	L7	i=7 arr[i]=8 top=4	The stack top survives, so stop popping.
26	L10	i=7	Push index 7.
27	L12	return=[7, 9, 5, 9, -1, 6, 8, -1]	Indices still on the stack have no greater value to their right, so they keep -1. 8 pushs and 6 pops: O(n).

12.04.2

Previous greater/smaller

For the previous greater element, scan left to right and pop everything not greater than the current value; whatever remains on top (if anything) is the previous greater element, and then the current index is pushed. The previous smaller element is the mirror image. The nearest-smaller variants are the basis of the histogram and span problems.

Switch to the previous-greater animation to compare.

Java

1static int[] previousGreater(int[] a) {
2    int[] ans = new int[a.length];
3    Deque<Integer> stack = new ArrayDeque<>();               // values in decreasing order from bottom to top
4    for (int i = 0; i < a.length; i++) {
5        while (!stack.isEmpty() && a[stack.peek()] <= a[i]) stack.pop();
6        ans[i] = stack.isEmpty() ? -1 : a[stack.peek()];
7        stack.push(i);
8    }
9    return ans;
10}

Previous greater element

Interactive · edit the input

int[] arr · length 8

01234567

CurrentOn the stackAnswered

stack (bottom→top)

empty

result[]

·0

·1

·2

·3

·4

·5

·6

·7

Setup

The stack holds indices whose values decrease from bottom to top. Each index is pushed once and popped at most once, so the whole scan is O(n).

Step 1 / 35

Java

1public static int[] previousGreater(int[] arr) {
2    int n = arr.length;
3    int[] result = new int[n];
4    Arrays.fill(result, -1);
5    Deque<Integer> stack = new ArrayDeque<>();      // indices; their values decrease bottom to top
6    for (int i = 0; i < n; i++) {
7        while (!stack.isEmpty() && arr[stack.peek()] <= arr[i]) {
8            stack.pop();                           // can never be a previous greater again
9        }
10        if (!stack.isEmpty()) result[i] = arr[stack.peek()];
11        stack.push(i);
12    }
13    return result;
14}

Live state

0 pushes0 pops

No condition evaluated on this step

Execution trace (dry run table)Show 35 steps

Step	Line	State	What happens
1	L5	n=8	The stack holds indices whose values decrease from bottom to top. Each index is pushed once and popped at most once, so the whole scan is O(n).
2	L10	i=0 result[i]=-1	The stack is empty: nothing before index 0 is greater, so result[0] = -1.
3	L11	i=0	Push index 0.
4	L7	i=1 arr[i]=7 top=0	4 is blocked by 7 for every later index, so it can be discarded.
5	L8	i=1 popped=0	Popped index 0.
6	L10	i=1 result[i]=-1	The stack is empty: nothing before index 1 is greater, so result[1] = -1.
7	L11	i=1	Push index 1.
8	L7	i=2 arr[i]=3 top=1	The stack top survives, so stop popping.
9	L10	i=2 result[i]=7	The stack top 7 is the previous greater value for index 2.
10	L11	i=2	Push index 2.
11	L7	i=3 arr[i]=5 top=2	3 is blocked by 5 for every later index, so it can be discarded.
12	L8	i=3 popped=2	Popped index 2.
13	L7	i=3 arr[i]=5 top=1	The stack top survives, so stop popping.
14	L10	i=3 result[i]=7	The stack top 7 is the previous greater value for index 3.
15	L11	i=3	Push index 3.
16	L7	i=4 arr[i]=9 top=3	5 is blocked by 9 for every later index, so it can be discarded.
17	L8	i=4 popped=3	Popped index 3.
18	L7	i=4 arr[i]=9 top=1	7 is blocked by 9 for every later index, so it can be discarded.
19	L8	i=4 popped=1	Popped index 1.
20	L10	i=4 result[i]=-1	The stack is empty: nothing before index 4 is greater, so result[4] = -1.
21	L11	i=4	Push index 4.
22	L7	i=5 arr[i]=2 top=4	The stack top survives, so stop popping.
23	L10	i=5 result[i]=9	The stack top 9 is the previous greater value for index 5.
24	L11	i=5	Push index 5.
25	L7	i=6 arr[i]=6 top=5	2 is blocked by 6 for every later index, so it can be discarded.
26	L8	i=6 popped=5	Popped index 5.
27	L7	i=6 arr[i]=6 top=4	The stack top survives, so stop popping.
28	L10	i=6 result[i]=9	The stack top 9 is the previous greater value for index 6.
29	L11	i=6	Push index 6.
30	L7	i=7 arr[i]=8 top=6	6 is blocked by 8 for every later index, so it can be discarded.
31	L8	i=7 popped=6	Popped index 6.
32	L7	i=7 arr[i]=8 top=4	The stack top survives, so stop popping.
33	L10	i=7 result[i]=9	The stack top 9 is the previous greater value for index 7.
34	L11	i=7	Push index 7.
35	L13	return=[-1, -1, 7, 7, -1, 9, 9, 9]	8 pushs and 6 pops: O(n).

12.04.3

Stock span

The span of day i is the number of consecutive days up to and including i whose price is at most the price on day i. Keep a stack of indexes with strictly decreasing prices: pop every index with a price not above today's; the span is today's index minus the new top (or i + 1 when the stack is empty). O(n) overall.

Try the classic price series and the rising and falling cases.

Java

1static int[] stockSpan(int[] price) {
2    int[] span = new int[price.length];
3    Deque<Integer> stack = new ArrayDeque<>();
4    for (int i = 0; i < price.length; i++) {
5        while (!stack.isEmpty() && price[stack.peek()] <= price[i]) stack.pop();
6        span[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
7        stack.push(i);
8    }
9    return span;
10}

Stock span with a monotonic stack

Interactive · edit the input

int[] arr · length 7

100

0123456

Today's priceDays in today's spanPopped (swallowed)Blocker still on the stack

stack of indexes (top is last)

empty

span so far

none yet

Setup

The span of day i counts consecutive earlier days with a price at most today's, plus today. The stack keeps only days whose price is higher than everything after them.

Step 1 / 14

Java

1static int[] stockSpan(int[] price) {
2    int[] span = new int[price.length];
3    Deque<Integer> stack = new ArrayDeque<>();                  // indexes of prices that can still block later days
4    for (int i = 0; i < price.length; i++) {
5        while (!stack.isEmpty() && price[stack.peek()] <= price[i]) stack.pop();   // smaller or equal prices are swallowed
6        span[i] = stack.isEmpty() ? i + 1 : i - stack.peek();                      // days since the last higher price
7        stack.push(i);
8    }
9    return span;
10}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 14 steps

Step	Line	State	What happens
1	L3		The span of day i counts consecutive earlier days with a price at most today's, plus today. The stack keeps only days whose price is higher than everything after them.
2	L6	i=0 price=100 span=1	The stack is empty, so no earlier price was higher: span = 0 + 1 = 1.
3	L6	i=1 price=80 span=1	The nearest higher price is day 0 (100): span = 1 - 0 = 1.
4	L6	i=2 price=60 span=1	The nearest higher price is day 1 (80): span = 2 - 1 = 1.
5	L5	i=3 price=70 popped=2:60	Day 2 (60) <= 70: it can never block a later day that today does not also beat, so pop it.
6	L6	i=3 price=70 span=2	The nearest higher price is day 1 (80): span = 3 - 1 = 2.
7	L6	i=4 price=60 span=1	The nearest higher price is day 3 (70): span = 4 - 3 = 1.
8	L5	i=5 price=75 popped=4:60	Day 4 (60) <= 75: it can never block a later day that today does not also beat, so pop it.
9	L5	i=5 price=75 popped=3:70	Day 3 (70) <= 75: it can never block a later day that today does not also beat, so pop it.
10	L6	i=5 price=75 span=4	The nearest higher price is day 1 (80): span = 5 - 1 = 4.
11	L5	i=6 price=85 popped=5:75	Day 5 (75) <= 85: it can never block a later day that today does not also beat, so pop it.
12	L5	i=6 price=85 popped=1:80	Day 1 (80) <= 85: it can never block a later day that today does not also beat, so pop it.
13	L6	i=6 price=85 span=6	The nearest higher price is day 0 (100): span = 6 - 0 = 6.
14	L9	return=[1, 1, 1, 2, 1, 4, 6]	Spans [1, 1, 1, 2, 1, 4, 6]. Each index is pushed and popped at most once: O(n) overall, although one day may pop many.

12.04.4

Daily temperatures

For each day, how many days until a warmer temperature? This is next greater element with distances: when day i is warmer than the stack top j, the answer for j is i - j. Days left on the stack never see a warmer day and keep 0.

Run the classic temperature list.

Java

1static int[] dailyTemperatures(int[] t) {
2    int[] ans = new int[t.length];
3    Deque<Integer> stack = new ArrayDeque<>();
4    for (int i = 0; i < t.length; i++) {
5        while (!stack.isEmpty() && t[stack.peek()] < t[i]) {
6            int j = stack.pop();
7            ans[j] = i - j;
8        }
9        stack.push(i);
10    }
11    return ans;
12}

Daily temperatures: days until a warmer day

Interactive · edit the input

int[] arr · length 8

01234567

TodayResolved by todayWaiting on the stack

waiting (index:temperature, top is last)

empty

answer so far

Setup

Each day waits on the stack until a warmer day arrives; that day answers every colder day below it.

Step 1 / 16

Java

1static int[] dailyTemperatures(int[] t) {
2    int[] ans = new int[t.length];                           // 0 means no warmer day ahead
3    Deque<Integer> stack = new ArrayDeque<>();               // days still waiting for a warmer day (temperatures fall toward the top)
4    for (int i = 0; i < t.length; i++) {
5        while (!stack.isEmpty() && t[stack.peek()] < t[i]) {
6            int j = stack.pop();
7            ans[j] = i - j;                                   // today is the first warmer day for j
8        }
9        stack.push(i);
10    }
11    return ans;
12}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 16 steps

Step	Line	State	What happens
1	L3		Each day waits on the stack until a warmer day arrives; that day answers every colder day below it.
2	L9	i=0 temp=73	Push day 0: it is still waiting for a warmer day.
3	L7	i=1 j=0 ans[j]=1	Day 1 (74) is warmer than day 0 (73): ans[0] = 1 - 0 = 1.
4	L9	i=1 temp=74	Push day 1: it is still waiting for a warmer day.
5	L7	i=2 j=1 ans[j]=1	Day 2 (75) is warmer than day 1 (74): ans[1] = 2 - 1 = 1.
6	L9	i=2 temp=75	Push day 2: it is still waiting for a warmer day.
7	L9	i=3 temp=71	Push day 3: it is still waiting for a warmer day.
8	L9	i=4 temp=69	Push day 4: it is still waiting for a warmer day.
9	L7	i=5 j=4 ans[j]=1	Day 5 (72) is warmer than day 4 (69): ans[4] = 5 - 4 = 1.
10	L7	i=5 j=3 ans[j]=2	Day 5 (72) is warmer than day 3 (71): ans[3] = 5 - 3 = 2.
11	L9	i=5 temp=72	Push day 5: it is still waiting for a warmer day.
12	L7	i=6 j=5 ans[j]=1	Day 6 (76) is warmer than day 5 (72): ans[5] = 6 - 5 = 1.
13	L7	i=6 j=2 ans[j]=4	Day 6 (76) is warmer than day 2 (75): ans[2] = 6 - 2 = 4.
14	L9	i=6 temp=76	Push day 6: it is still waiting for a warmer day.
15	L9	i=7 temp=73	Push day 7: it is still waiting for a warmer day.
16	L11	return=[1, 1, 4, 2, 1, 1, 0, 0]	Answers [1, 1, 4, 2, 1, 1, 0, 0]. Days left on the stack never see a warmer day, so they keep 0. O(n) time.

12.04.5

Largest rectangle in histogram

The largest rectangle in a histogram: for every bar, the widest rectangle using that bar's height extends left and right until a shorter bar. A stack of increasing bar heights finds those limits: when a shorter bar arrives, pop each taller bar, and its rectangle spans from the new stack top (the nearest shorter bar on the left) to the current index (the nearest shorter bar on the right). A final height of 0 flushes the stack. O(n), compared with O(n²) for trying every pair of bounds.

Step through the classic histogram [2, 1, 5, 6, 2, 3] and watch each rectangle being measured.

Java

1static int largestRectangle(int[] h) {
2    Deque<Integer> stack = new ArrayDeque<>();
3    int best = 0;
4    for (int i = 0; i <= h.length; i++) {
5        int cur = i == h.length ? 0 : h[i];
6        while (!stack.isEmpty() && h[stack.peek()] >= cur) {
7            int height = h[stack.pop()];
8            int left = stack.isEmpty() ? -1 : stack.peek();
9            best = Math.max(best, height * (i - left - 1));
10        }
11        stack.push(i);
12    }
13    return best;
14}

Largest rectangle in a histogram

Interactive · edit the input

int[] arr · length 6

0123456

Bar being processedRectangle just measuredOn the stack (increasing heights)

stack of bar indexes (top is last)

empty

Setup

Keep a stack of bars with increasing heights. A shorter bar ends the rectangles of the taller bars on the stack.

Step 1 / 14

Java

1static int largestRectangle(int[] h) {
2    Deque<Integer> stack = new ArrayDeque<>(); int best = 0;
3    for (int i = 0; i <= h.length; i++) {
4        int cur = i == h.length ? 0 : h[i];                          // a final height 0 flushes the stack
5        while (!stack.isEmpty() && h[stack.peek()] >= cur) {
6            int height = h[stack.pop()];
7            int left = stack.isEmpty() ? -1 : stack.peek();          // nearest shorter bar on the left
8            best = Math.max(best, height * (i - left - 1));          // widest rectangle with this height
9        }
10        stack.push(i);
11    }
12    return best;
13}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 14 steps

Step	Line	State	What happens
1	L2		Keep a stack of bars with increasing heights. A shorter bar ends the rectangles of the taller bars on the stack.
2	L10	i=0 best=0	Push bar 0 (2): the stack stays increasing.
3	L8	i=1 height=2 width=1 area=2 best=2	Bar 1 (1) is not taller than bar 0 (2), so the rectangle of height 2 cannot extend further: width 1 - -1 - 1 = 1, area 2. Best 2.
4	L10	i=1 best=2	Push bar 1 (1): the stack stays increasing.
5	L10	i=2 best=2	Push bar 2 (5): the stack stays increasing.
6	L10	i=3 best=2	Push bar 3 (6): the stack stays increasing.
7	L8	i=4 height=6 width=1 area=6 best=6	Bar 4 (2) is not taller than bar 3 (6), so the rectangle of height 6 cannot extend further: width 4 - 2 - 1 = 1, area 6. Best 6.
8	L8	i=4 height=5 width=2 area=10 best=10	Bar 4 (2) is not taller than bar 2 (5), so the rectangle of height 5 cannot extend further: width 4 - 1 - 1 = 2, area 10. Best 10.
9	L10	i=4 best=10	Push bar 4 (2): the stack stays increasing.
10	L10	i=5 best=10	Push bar 5 (3): the stack stays increasing.
11	L8	i=6 height=3 width=1 area=3 best=10	End of the histogram is not taller than bar 5 (3), so the rectangle of height 3 cannot extend further: width 6 - 4 - 1 = 1, area 3. Best 10.
12	L8	i=6 height=2 width=4 area=8 best=10	End of the histogram is not taller than bar 4 (2), so the rectangle of height 2 cannot extend further: width 6 - 1 - 1 = 4, area 8. Best 10.
13	L8	i=6 height=1 width=6 area=6 best=10	End of the histogram is not taller than bar 1 (1), so the rectangle of height 1 cannot extend further: width 6 - -1 - 1 = 6, area 6. Best 10.
14	L12	return=10	Largest rectangle area: 10. Each bar is pushed and popped once: O(n), against O(n²) for trying every pair of bounds.

Practice ladder

Now try it yourself

Easy

Next greater element of [2, 1, 3] by hand
Stock span of [10, 4, 5, 90, 80]

Medium

Daily temperatures for [30, 40, 50, 60]
Why is the monotonic stack solution O(n) although it contains a while loop?

Advanced

Largest rectangle of 1s in a binary matrix using the histogram method on each row

Key takeaways

Keep a stack of indexes in monotonic order; pop when the current value settles them.
Each element is pushed once and popped once, so the pattern is O(n).
Histogram: popping a bar fixes its rectangle between the nearest shorter bars.