15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A monotonic stack is a stack that keeps its values in one order, such as non-increasing from bottom to top. Each new value pops the smaller entries it resolves, then gets pushed. Storing indices lets every pop write its answer in place. Each index is pushed and popped at most once, so a full scan takes O(n) time.
| Stack order for next greater | values non-increasing from bottom to top, indices increasing |
|---|---|
| What it stores | indices of values that have no greater value to their right yet |
| Time | O(n), at most n pushes and n pops |
| Auxiliary space | O(n), the stack can hold every index |
| Equal values | do not resolve each other, the pop test is strict > |
| Use when | each element needs the nearest greater value on its right |
This lesson builds on these operations:
A monotonic structure stores candidates in one chosen value order.
We will store indices, not only values. An index tells us both the value and where an answer belongs.
For this lesson, “next greater” means strictly greater. Equal values do not resolve one another.
Reference material for the stack and queue foundations: Algorithms, 4th edition companion site. The operation-count approach in the complexity section follows the analyze-before-implement emphasis of this data structures and algorithms course outline.
Find the first strictly greater value to the right of every value in:
| Index | 0 | 1 | 2 |
|---|---|---|---|
| Value | 2 | 1 | 3 |
The required answer is:
| Index | 0 | 1 | 2 |
|---|---|---|---|
| Next greater value | 3 | 3 | -1 |
At index 0, the first larger value to its right is 3.
At index 1, the first larger value to its right is also 3.
At index 2, there is nothing to the right, so its answer stays -1.
Start with one answer slot per input position:
1answers = [-1, -1, -1]Use a stack of unresolved indices. “Unresolved” means we have not yet seen a strictly greater value to that index’s right.
1stack = []The stack will hold values in non-increasing order from bottom to top. A smaller value may sit above a larger value.
Start at index 0.
A monotonic stack finds each next greater value in one pass. Each index is pushed once and popped once; the value 3 resolves both earlier indices, and the last index keeps -1. Result: [3, 3, -1].
1answers = [-1, -1, -1]
2stack indices = []
3stack values = []The stack is empty. There is no earlier unresolved value for 2 to resolve.
Push index 0.
1answers = [-1, -1, -1]
2stack indices = [0]
3stack values = [2]Compare the current value, 1, with the stack-top value, 2.
11 > 2 is falseSo 1 does not resolve index 0. Push index 1 as another unresolved position.
1answers = [-1, -1, -1]
2stack indices = [0, 1]
3stack values = [2, 1]Compare 3 with the stack-top value, 1.
13 > 1 is truePop index 1. The current value, 3, is the first strictly greater value to the right of index 1.
1answers[1] = 3
2
3answers = [-1, 3, -1]
4stack indices = [0]
5stack values = [2]We are still processing index 2. The stack is not empty, so compare 3 with the new stack-top value, 2.
13 > 2 is truePop index 0 and record its answer.
1answers[0] = 3
2
3answers = [3, 3, -1]
4stack indices = []
5stack values = []Now no unresolved earlier index remains. Push index 2.
1answers = [3, 3, -1]
2stack indices = [2]
3stack values = [3]The input ends. Index 2 has no value to its right, so its answer remains -1.
1return [3, 3, -1]For a sliding-window maximum, use a deque whose values decrease from front to rear. The front is then the maximum candidate for the current window.
When a new value arrives:
k, report the front value.For equal values, this lesson removes the older rear value using <=. The newer equal value remains because it expires later.
A removed rear candidate cannot later become the maximum while the incoming larger-or-equal value remains in the window. The incoming value is at least as large and expires later because it has a larger index.
The stack states establish a rule that remains true.
For the next-greater scan:
This rule is the invariant.
Look back at the example after index 1:
1stack indices = [0, 1]
2stack values = [2, 1]The indices increase: 0, then 1.
The values do not increase: 2, then 1.
Neither index has found a greater value in the portion scanned after it:
0 has seen 1, which is not greater than 2.1 has not yet seen any value to its right.When value 3 arrives, it resolves every stack-top value smaller than 3. After those pops, pushing 3 restores the non-increasing value order.
For a sliding-window maximum deque, the matching rule is:
<= rear-removal policy.We scan from left to right because an element’s next greater value must appear to its right.
At each index i:
current be values[i].current is strictly greater than the value at the stack top:
j.current into answers[j].i.The order matters.
Do not push i first. Let the current value resolve all smaller unresolved values, then place the current index on the stack as a new unresolved candidate.
One current value can resolve several indices because the stack top is the most recently seen unresolved index. If the current value is greater than it, that current value is its first greater value to the right. After removing it, the next stack entry may also be smaller, so the same current value may resolve that entry too.
For the sliding-window maximum, the deque uses candidate removal and also removes positions outside the window. An index i is expired when:
1i <= currentIndex - kThat condition means i lies before the window’s left boundary.
Input: values, an array of integers of length n.
Return: A new array answers of length n. answers[i] is the first strictly greater value to the right of values[i], or -1 if none exists.
Mutation behavior: Does not modify values.
Helper contract: top(stack) returns the most recently pushed index without removing it. It is called only when stack is nonempty.
11 function nextGreaterValues(values):
22 n = length(values)
33 answers = new array of length n, filled with -1
44 stack = empty stack of indices
55
66 for i from 0 to n - 1:
77 while stack is not empty AND values[i] > values[top(stack)]:
88 resolvedIndex = pop(stack)
99 answers[resolvedIndex] = values[i]
1010
1111 push(stack, i)
1212
1313 return answersThe strict comparison on line 7 is required. With a strictly greater definition, equal values remain unresolved.
Input: values, an array of integers, and k, a window width.
Return: A new array containing one maximum per complete width-k window. If k < 1 or k > length(values), return INVALID_WINDOW.
Mutation behavior: Does not modify values.
Helper contract: front(deque) and rear(deque) return stored indices without removing them. They are called only when the deque is nonempty.
1function slidingWindowMaximum(values, k):
2 n = length(values)
3
4 if k < 1 OR k > n:
5 return INVALID_WINDOW
6
7 maximums = empty list
8 deque = empty deque of indices
9
10 for i from 0 to n - 1:
11 while deque is not empty AND front(deque) <= i - k:
12 removeFront(deque)
13
14 while deque is not empty AND values[rear(deque)] <= values[i]:
15 removeRear(deque)
16
17 addRear(deque, i)
18
19 if i >= k - 1:
20 append maximums, values[front(deque)]
21
22 return maximumsThe <= comparison keeps the newer of equal values. A different equal-value policy is possible, but the comparison and explanation must agree.
Use the original input:
1values = [2, 1, 3]1n = 3
2answers = [-1, -1, -1]
3stack = []At line 7, stack is empty. The while condition is false.
Line 11 pushes 0.
1answers = [-1, -1, -1]
2stack indices = [0]
3stack values = [2]At line 7:
1values[1] > values[top(stack)]
21 > values[0]
31 > 2The condition is false.
Line 11 pushes 1.
1answers = [-1, -1, -1]
2stack indices = [0, 1]
3stack values = [2, 1]At line 7:
1values[2] > values[top(stack)]
23 > values[1]
33 > 1The condition is true.
Line 8 pops index 1.
1resolvedIndex = 1
2stack indices = [0]Line 9 writes the current value into that answer position.
1answers[1] = values[2] = 3
2answers = [-1, 3, -1]Control returns to line 7.
1values[2] > values[top(stack)]
23 > values[0]
33 > 2The condition is true again.
Line 8 pops index 0.
1resolvedIndex = 0
2stack indices = []Line 9 writes:
1answers[0] = values[2] = 3
2answers = [3, 3, -1]Control returns to line 7. The stack is empty, so the condition is false.
Line 11 pushes index 2.
1stack indices = [2]
2stack values = [3]The for loop ends. Line 13 returns:
1[3, 3, -1]We show that nextGreaterValues returns the first strictly greater value to the right for every input position.
Before the loop, the stack is empty.
Therefore:
So the invariant holds before the first iteration.
Assume the invariant holds before processing index i.
The algorithm examines the stack top while:
1values[i] > values[top(stack)]Suppose it pops index j.
Because j is still on the stack, it is unresolved. By the invariant, no earlier scanned value to the right of j was strictly greater than values[j].
The current index i is scanned after all those earlier positions, and values[i] > values[j]. Therefore values[i] is the first strictly greater value to the right of index j. Writing it to answers[j] is correct.
The algorithm removes no index unless the current value resolves it. An unresolved index is never discarded without an answer.
When the pop loop stops, either the stack is empty or the stack-top value is greater than or equal to values[i]. Pushing i then preserves non-increasing values from stack bottom to stack top. The new index is unresolved, and no previously scanned value lies to its right. The invariant holds for the next iteration.
The loop ends after every index has been scanned.
Any index removed from the stack received its first strictly greater value when it was popped.
Any index left on the stack has never encountered a later strictly greater value. Its initialized answer remains -1, which is the specified no-next-greater result.
Therefore the returned array is correct for every position.
For the sliding-window deque, correctness also requires removing expired front indices before reporting the front. After expired indices are removed, all deque entries belong to the current window. The decreasing value order means no entry behind the front has a larger value, so the front reports the window maximum.
Consider an input of length n.
Each index is pushed onto the next-greater stack exactly once.
An index can be popped only after it was pushed. Therefore, across the entire scan, there are at most n pops.
So the total stack operations are at most:
1n pushes + n pops = at most 2n stack operationsThere is also constant work per loop check, comparison, and answer write. The total time is therefore:
1O(n)The O(n) bound covers the entire scan, not each input item.
The stack can contain at most all n indices at once, so its auxiliary space is:
1O(n)The returned answers array is output storage and also has length n.
For sliding-window maximum with width k, each index enters the deque once and can leave at most once, either from the front as expired or from the rear as dominated. The total deque operations are linear in n, so the time is O(n). The deque contains at most k active indices, so its auxiliary space is O(k).
>= for a strictly greater taskIncorrect condition:
1while values[i] >= values[top(stack)]:Exposing input:
1[2, 2]The first 2 is popped when the second 2 arrives, and the incorrect implementation writes:
1[2, -1]Equal is not strictly greater. The correct result is:
1[-1, -1]Correction: Use:
1values[i] > values[top(stack)]Incorrect assumption: Store only stack values.
Exposing input:
1[2, 1, 3]When 3 arrives, it resolves both pending values 1 and 2. If the stack holds only values, the algorithm no longer knows which answer positions to write:
1answers[1] = 3
2answers[0] = 3Correction: Store indices. Recover a value with values[index], and write the result to answers[index].
Incorrect order:
1push(stack, i)
2while stack is not empty AND values[i] > values[top(stack)]:
3 ...Exposing input:
1[2, 1, 3]After pushing index 2, the stack top is index 2 itself. The comparison becomes:
13 > 3which is false. The earlier 1 and 2 are not resolved.
Correction: Pop every smaller unresolved top first. Push the current index only after the pop loop ends.
Incorrect assumption: The deque front may remain even after it leaves the window.
Exposing input:
1values = [9, 1, 1]
2k = 2For the second window, indices 1 and 2, index 0 is expired. If it remains at the front, the algorithm incorrectly reports 9.
The correct maximum for [1, 1] is 1.
Correction: Before reporting a window maximum at current index i, remove front indices satisfying:
1front(deque) <= i - k| Input or setting | Required result |
|---|---|
[] | Return []. |
[5] | Return [-1]. |
[1, 2, 3] | Return [2, 3, -1]. |
[3, 2, 1] | Return [-1, -1, -1]. |
[2, 2] with strict comparison | Return [-1, -1]. |
Sliding window with k = 1 | Each output equals the corresponding input value. |
Sliding window with k > length(values) | Return the documented invalid-window result, INVALID_WINDOW, in this pseudocode. |
Objective: Given an integer array, return an array in which each position contains the first strictly greater value to its right or -1 if none exists.
The practice tests the next-greater stack contract:
1def next_greater_values(values):
2 n = len(values)
3 answers = [-1] * n
4 stack = [] # indices of unresolved values
5 for i in range(n):
6 while stack and values[i] > values[stack[-1]]: # strict: equal does not resolve
7 resolved = stack.pop()
8 answers[resolved] = values[i]
9 stack.append(i) # push after the pops
10 return answers
11
12for values in ([2, 1, 3], [1, 2, 3], [3, 2, 1], [2, 2], []):
13 print(values, "->", next_greater_values(values))1import java.util.ArrayDeque;
2import java.util.Arrays;
3import java.util.Deque;
4
5public class Main {
6 static int[] nextGreaterValues(int[] values) {
7 int n = values.length;
8 int[] answers = new int[n];
9 Arrays.fill(answers, -1);
10 Deque<Integer> stack = new ArrayDeque<>(); // indices of unresolved values
11 for (int i = 0; i < n; i++) {
12 while (!stack.isEmpty() && values[i] > values[stack.peek()]) { // strict: equal does not resolve
13 int resolved = stack.pop();
14 answers[resolved] = values[i];
15 }
16 stack.push(i); // push after the pops
17 }
18 return answers;
19 }
20
21 public static void main(String[] args) {
22 int[][] inputs = {{2, 1, 3}, {1, 2, 3}, {3, 2, 1}, {2, 2}, {}};
23 for (int[] values : inputs) {
24 System.out.println(Arrays.toString(values) + " -> " + Arrays.toString(nextGreaterValues(values)));
25 }
26 }
27}1#include <iostream>
2#include <stack>
3#include <vector>
4using namespace std;
5
6vector<int> nextGreaterValues(const vector<int>& values) {
7 int n = values.size();
8 vector<int> answers(n, -1);
9 stack<int> st; // indices of unresolved values
10 for (int i = 0; i < n; i++) {
11 while (!st.empty() && values[i] > values[st.top()]) { // strict: equal does not resolve
12 int resolved = st.top();
13 st.pop();
14 answers[resolved] = values[i];
15 }
16 st.push(i); // push after the pops
17 }
18 return answers;
19}
20
21void show(const vector<int>& v) {
22 cout << "[";
23 for (size_t i = 0; i < v.size(); i++) cout << (i ? ", " : "") << v[i];
24 cout << "]";
25}
26
27int main() {
28 vector<vector<int>> inputs = {{2, 1, 3}, {1, 2, 3}, {3, 2, 1}, {2, 2}, {}};
29 for (const auto& values : inputs) {
30 show(values);
31 cout << " -> ";
32 show(nextGreaterValues(values));
33 cout << endl;
34 }
35}1function nextGreaterValues(values) {
2 const n = values.length;
3 const answers = new Array(n).fill(-1);
4 const stack = []; // indices of unresolved values
5 for (let i = 0; i < n; i++) {
6 while (stack.length && values[i] > values[stack[stack.length - 1]]) { // strict: equal does not resolve
7 const resolved = stack.pop();
8 answers[resolved] = values[i];
9 }
10 stack.push(i); // push after the pops
11 }
12 return answers;
13}
14
15for (const values of [[2, 1, 3], [1, 2, 3], [3, 2, 1], [2, 2], []]) {
16 console.log(`[${values.join(', ')}] -> [${nextGreaterValues(values).join(', ')}]`);
17}It depends on the question. For the next strictly greater value, the stored values are non-increasing from bottom to top, but sources name this order differently, so state the order you keep. Flip the comparison and the same scan finds the next smaller value.
Each index is pushed once and can be popped only after that, so there are at most n pushes and n pops in the whole scan. The inner loop does not restart for each element. Total work is at most 2n stack operations.
A pop must know which answer slot to fill. On [2, 1, 3], the value 3 resolves two entries, and only their indices tell you to write answers[1] and answers[0]. You still read a value with values[index].
The stack pops from one end, the top, and fits next-greater questions. A monotonic queue is a deque that also drops expired indices from the front, which a sliding-window maximum needs. That has its own page, linked below.
For [2, 2] with a strict comparison, it returns [-1, -1]. Equal is not strictly greater, so the second 2 does not resolve the first. Using >= would wrongly give [2, -1].