Next Greater Element
Next Greater Element is a GFG problem (Medium). You are given an array arr of integers. For every position, find its next greater element: the first value to its right that is strictly larger.
- Look only to the right of the position.
- Take the first larger value you meet, not the largest one.
- Equal values do not count; the answer must be strictly bigger.
- If nothing to the right is larger, the answer for that position is
-1.
Return an array of the same length whose entry i is the answer for arr[i].
- 1 <= n <= 10⁵
- 1 <= nums[i] <= 10⁹
- Return -1 where no greater element exists
Intuition
Walking right from every index until something bigger turns up is O(n²) on a decreasing array, and most of that walking is repeated.
Flip the question: instead of each element searching for its answer, let it wait for the answer to walk past. Scan left to right and keep the indices still waiting. A new value is the answer for every waiting element it beats, because it is to their right, it is larger, and it is the first such value they have met.
- The waiting values decrease from the bottom of the stack to the top.
A new value removes every smaller waiter before it joins, so the order never breaks. That is the monotonic stack: once the top is not beaten, nothing below it can be.
"For each element, find the nearest bigger (or smaller) one to the left or right" is the signature of a monotonic stack. The same next greater element stack answers Daily Temperatures, Stock Span, Largest Rectangle in Histogram and Next Greater Element II; only the comparison and the scan direction change.
Approach
Before reading on: for [2, 7, 3, 5, 4, 6, 8], which elements are still waiting for an answer just before 6 arrives, and in what order are their values? Aim for O(n) time.
Keep indices, not values
The stack holds indices whose answer is still unknown. An index tells you where to write the answer when it arrives, and it keeps equal values apart. Fill the result with -1 up front so the no-answer case needs no extra code.
Resolve every waiter the new value beats
For each index i, left to right: while the stack is not empty and arr[top] < arr[i], pop top and set res[top] = arr[i]. It is a while, not an if: one big value can settle a whole run of smaller waiters at once.
Stop at the first waiter that is not smaller
When the top is greater than or equal to arr[i], stop. Everything below it is larger still, so none of it can be beaten either. Then push i: it becomes the newest waiter, and the stack stays decreasing.
Leave the survivors at -1
Indices still on the stack after the scan never met a larger value to their right. Their slots already hold -1 from the start, so res can be returned as it is.
Scanning from the right works too
Many next greater element solutions walk right to left instead: pop every value ≤ arr[i], because they are hidden behind arr[i] for everything further left, read the answer off the top, then push arr[i]. It is the same O(n) decreasing stack, but it stores values, and each element gets its answer when it is processed.
Next Greater Element solution in Python | C++ | Java
res with -1. Think of each bar as looking right: its answer is the first taller bar that blocks the view. Bars that never get blocked keep -1, so starting there means the leftovers need no work at the end.res[0]. The stack is now empty.res[2]. Next on top is 5.res[1]. This is the second pop for the same 25: the while keeps going while the top is smaller. The stack is now empty.res with -1. Think of each bar as looking right: its answer is the first taller bar that blocks the view. Bars that never get blocked keep -1, so starting there means the leftovers need no work at the end.res[2]. Next on top is 7.res[1]. This is the second pop for the same 12: the while keeps going while the top is smaller. Next on top is 13.res with -1. Think of each bar as looking right: its answer is the first taller bar that blocks the view. Bars that never get blocked keep -1, so starting there means the leftovers need no work at the end.res[1]. Next on top is 2.res[2]. Next on top is 2.res[0]. This is the second pop for the same 4: the while keeps going while the top is smaller. The stack is now empty.res with -1. Think of each bar as looking right: its answer is the first taller bar that blocks the view. Bars that never get blocked keep -1, so starting there means the leftovers need no work at the end.Common pitfalls
Pushing values instead of indices
while stack and stack[-1] < arr[i]:
stack.pop()
stack.append(arr[i])while stack and arr[stack[-1]] < arr[i]:
res[stack.pop()] = arr[i]
stack.append(i)In the left-to-right scan the answer is found for the popped element, not the current one. With only its value you cannot tell which slot of res to fill, and with duplicates you cannot even guess.
Popping on equal values
while stack and arr[stack[-1]] <= arr[i]:
while stack and arr[stack[-1]] < arr[i]:
<= hands an element an answer that is equal to it. For [2, 1, 2, 4] the first 2 would get 2 instead of 4. In this direction the comparison must be strict; in the right-to-left version it is the other way round (pop <=).
Edge cases
No value ever beats the top, so nothing is popped and every index is still waiting at the end: all answers are -1. This is also when the stack is largest, holding all n indices.
An equal value stops the popping and waits on top of its twin. Both are then answered by the same later, larger value, which is correct: neither twin is the other's next greater element.
Complexity
while looks nested, but each index is pushed once and popped at most once, so the whole scan does at most 2n stack operations. Space is the stack, which holds every index for a strictly decreasing array.Which next greater element problem is it?
Searching next greater element leetcode turns up three problems that share the name. The stack is the same in all of them; the input and where the scan wraps are not.
| Problem | Input | What changes |
|---|---|---|
| Next Greater Element (GFG) | one array | the scan on this page |
| Next Greater Element I (LeetCode 496) | nums1, a subset of nums2 | run the scan on nums2, store answers in a map by value, then look up each nums1 value |
| Next Greater Element II (LeetCode 503) | a circular array | loop i from 0 to 2n - 1 using i % n, so waiters at the end can be answered by the start |
| Next Greater Element III (LeetCode 556) | one integer | not a stack problem: it is next permutation on the digits |
Next Greater Element FAQ
How does the next greater element stack work?
- Holds: indices whose next greater element is not known yet, with values decreasing from bottom to top.
- Each step: while the top's value is smaller than the current value, pop it and record the current value as its answer; then push the current index.
- End: indices left on the stack get
-1. - Complexity: O(n) time, O(n) space.
- Example:
[4, 5, 2, 25]gives[5, 25, 25, -1].
Why is the next greater element solution O(n) with a loop inside a loop?
Count stack operations instead of loop iterations. Every index is pushed exactly once and popped at most once, so across the whole scan the inner loop runs at most n times in total. The work is spread over the outer loop, not repeated for each element.
What is a monotonic stack?
A stack whose values stay sorted from bottom to top. Before pushing, you pop everything that would break the order, and each pop is where the answer is found. A decreasing stack finds next greater elements; an increasing one finds next smaller elements.
How do you write next greater element in Python?
Use a plain list as the stack: append pushes and pop() pops the last item, both O(1). Pre-fill res = [-1] * n, and write res[stack.pop()] = arr[i] inside the while, which pops the index and fills its slot in one line.
How is the next greater element leetcode version different?
LeetCode 496 gives two arrays: find the next greater element in nums2 for each value of nums1. Run this scan on nums2, save each answer in a dictionary keyed by value (the values are distinct), then read off the nums1 values. LeetCode 503 is the circular version.