7.05Beginner6 topics20 min5 interactive animations

Monotonic structures

A monotonic stack or deque keeps its elements in increasing or decreasing order by throwing away elements that can never matter again. It answers “nearest larger or smaller” and “window maximum” questions in O(n).

Learning goals

Find the next and previous greater or smaller element for every index
Explain why each element is pushed and popped at most once
Maintain a sliding window maximum with a monotonic deque
Choose between strict and non-strict comparisons for duplicates

Prerequisites

Stacks and dequesSliding windows

Standing in a line of people, which taller person blocks your view to the right? Anyone shorter than a newcomer will be hidden behind that newcomer for everyone further left, so you can forget them.

7.05.1

Next greater

Scan left to right and keep a stack of indices still waiting for their answer. Their values decrease from bottom to top. When a new value is larger than the top, it is the next greater element for that index: pop it and record the answer, and repeat.

Indices left on the stack at the end have no greater value to their right and get -1. Try the “Increasing” preset (each element is answered by its right neighbour, except the last) and the “Decreasing” one (nothing is ever answered, so everything stays -1).

Worst

O(n)

Space

O(n)

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).

7.05.2

Next smaller

Flip the comparison: pop while the top is larger than the new value. The stack values increase from bottom to top.

Next-smaller boundaries are what “largest rectangle in a histogram” needs: each bar extends left and right until it meets a smaller bar.

Next smaller 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 increase from bottom to top. Each index is pushed once and popped at most once, so the whole scan is O(n).

Step 1 / 25

Java

1public static int[] nextSmaller(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 increase 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 25 steps

Step	Line	State	What happens
1	L5	n=8	The stack holds indices whose values increase 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	The stack top survives, so stop popping.
4	L10	i=1	Push index 1.
5	L7	i=2 arr[i]=3 top=1	3 is the first smaller value to the right of index 1.
6	L8	i=2 popped=1	result[1] = 3.
7	L7	i=2 arr[i]=3 top=0	3 is the first smaller value to the right of index 0.
8	L8	i=2 popped=0	result[0] = 3.
9	L10	i=2	Push index 2.
10	L7	i=3 arr[i]=5 top=2	The stack top survives, so stop popping.
11	L10	i=3	Push index 3.
12	L7	i=4 arr[i]=9 top=3	The stack top survives, so stop popping.
13	L10	i=4	Push index 4.
14	L7	i=5 arr[i]=2 top=4	2 is the first smaller value to the right of index 4.
15	L8	i=5 popped=4	result[4] = 2.
16	L7	i=5 arr[i]=2 top=3	2 is the first smaller value to the right of index 3.
17	L8	i=5 popped=3	result[3] = 2.
18	L7	i=5 arr[i]=2 top=2	2 is the first smaller value to the right of index 2.
19	L8	i=5 popped=2	result[2] = 2.
20	L10	i=5	Push index 5.
21	L7	i=6 arr[i]=6 top=5	The stack top survives, so stop popping.
22	L10	i=6	Push index 6.
23	L7	i=7 arr[i]=8 top=6	The stack top survives, so stop popping.
24	L10	i=7	Push index 7.
25	L12	return=[3, 3, 2, 2, 2, -1, -1, -1]	Indices still on the stack have no smaller value to their right, so they keep -1. 8 pushs and 5 pops: O(n).

7.05.3

Previous greater

For the previous greater element, the answer for index i is already on the stack when i arrives. Pop every value that is less than or equal to arr[i], since i blocks them from being anyone's previous greater, and the remaining top is the answer.

Stock span uses exactly this: the span of day i is the distance back to the previous greater price.

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();   // distance to the previous greater price
7        stack.push(i);
8    }
9    return span;
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).

7.05.4

Monotonic stacks

The general rule: before pushing a new element, pop everything it makes useless. Each index is pushed once and popped at most once, so a full scan is O(n) even though there is a loop inside the loop.

The comparison decides how duplicates behave. With < for next greater, an equal value does not pop, so equal elements are not each other's answer. With <=, they are. Choose based on the problem's definition of “greater”.

Question	Scan	Pop while top is…	Stack order (bottom→top)
Next greater	left → right	< current	decreasing
Next smaller	left → right	> current	increasing
Previous greater	left → right	<= current	strictly decreasing
Previous smaller	left → right	>= current	strictly increasing

Previous smaller 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 increase from bottom to top. Each index is pushed once and popped at most once, so the whole scan is O(n).

Step 1 / 33

Java

1public static int[] previousSmaller(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 increase 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 smaller 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 33 steps

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

7.05.5

Monotonic queues

A monotonic deque is a monotonic stack that can also drop elements from the front. The front removes elements that have left a window by position; the back removes elements beaten by a newcomer by value.

Use ArrayDeque with peekFirst/pollFirst and peekLast/pollLast. Store indices, not values, so you can tell when the front has left the window.

Java

1Deque<Integer> dq = new ArrayDeque<>();   // indices, values decreasing front to back
2// window leaves:  if (dq.peekFirst() <= i - k) dq.pollFirst();
3// newcomer wins:  while (!dq.isEmpty() && arr[dq.peekLast()] <= arr[i]) dq.pollLast();
4// join:           dq.offerLast(i);
5// maximum:        arr[dq.peekFirst()]

7.05.6

Window minimum/maximum

The sliding window maximum keeps a decreasing deque. The front is always the largest value in the current window. Each index enters and leaves the deque once, so all n - k + 1 window maxima take O(n) total, compared with O(n · k) for rescanning every window.

For the window minimum, keep the deque increasing instead. Running both deques at once answers questions like “longest subarray where max − min ≤ limit”.

Worst

O(n)

Space

O(k)

Sliding window maximum (monotonic deque)

Interactive · edit the input

int[] arr · length 8

-1

-3

01234567

EnteringIn the dequeWindow maximum

deque (front→back)

empty

out[]

empty

Setup

The deque keeps only indices that could still become a window maximum, with their values decreasing. The front is always the current maximum.

Step 1 / 23

Java

1public static int[] maxSlidingWindow(int[] arr, int k) {
2    Deque<Integer> dq = new ArrayDeque<>();        // indices; values decrease front to back
3    int[] out = new int[arr.length - k + 1];
4    for (int i = 0; i < arr.length; i++) {
5        if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();   // fell out of the window
6        while (!dq.isEmpty() && arr[dq.peekLast()] <= arr[i]) dq.pollLast();
7        dq.offerLast(i);
8        if (i >= k - 1) out[i - k + 1] = arr[dq.peekFirst()];
9    }
10    return out;
11}

Live state

0 deque operations

No condition evaluated on this step

Execution trace (dry run table)Show 23 steps

Step	Line	State	What happens
1	L2	k=3	The deque keeps only indices that could still become a window maximum, with their values decreasing. The front is always the current maximum.
2	L7	i=0	Append index 0 (1).
3	L6	i=1 arr[i]=3 removed=0	1 is older and not larger than 3, so it can never be a maximum again. Remove it from the back.
4	L7	i=1	Append index 1 (3).
5	L7	i=2	Append index 2 (-1).
6	L8	i=2 max=3	Window [0..2] is full: its maximum is the deque front, 3.
7	L7	i=3	Append index 3 (-3).
8	L8	i=3 max=3	Window [1..3] is full: its maximum is the deque front, 3.
9	L5	i=4 removed=1	Index 1 has left the window [2..4], so drop it from the front.
10	L6	i=4 arr[i]=5 removed=3	-3 is older and not larger than 5, so it can never be a maximum again. Remove it from the back.
11	L6	i=4 arr[i]=5 removed=2	-1 is older and not larger than 5, so it can never be a maximum again. Remove it from the back.
12	L7	i=4	Append index 4 (5).
13	L8	i=4 max=5	Window [2..4] is full: its maximum is the deque front, 5.
14	L7	i=5	Append index 5 (3).
15	L8	i=5 max=5	Window [3..5] is full: its maximum is the deque front, 5.
16	L6	i=6 arr[i]=6 removed=5	3 is older and not larger than 6, so it can never be a maximum again. Remove it from the back.
17	L6	i=6 arr[i]=6 removed=4	5 is older and not larger than 6, so it can never be a maximum again. Remove it from the back.
18	L7	i=6	Append index 6 (6).
19	L8	i=6 max=6	Window [4..6] is full: its maximum is the deque front, 6.
20	L6	i=7 arr[i]=7 removed=6	6 is older and not larger than 7, so it can never be a maximum again. Remove it from the back.
21	L7	i=7	Append index 7 (7).
22	L8	i=7 max=7	Window [5..7] is full: its maximum is the deque front, 7.
23	L10	return=[3, 3, 5, 5, 6, 7]	6 windows answered with 15 deque operations: O(n), not O(n · k).

Practice ladder

Now try it yourself

Easy

Next greater element I
Final prices with a special discount

Medium

Daily temperatures
Online stock span
Sliding window maximum
Sum of subarray minimums

Advanced

Largest rectangle in histogram
Maximal rectangle
Longest continuous subarray with absolute diff ≤ limit

Key takeaways

Pop everything the new element makes useless, then push it; each index is pushed and popped at most once.
Next/previous greater/smaller differ only in scan direction and the comparison.
A monotonic deque gives every sliding window maximum or minimum in O(n).