Next Greater Element: How Do You Solve It?
Learn the monotonic stack approach to the next greater element problem and how to answer this common interview question.
Expected Interview Answer
The next greater element problem is solved with a monotonic decreasing stack: scan the array left to right keeping the stack's values in decreasing order, and whenever the current element is greater than the stack's top, pop the stack and record the current element as that popped index's next greater element, giving O(n) time instead of the brute-force O(n^2).
Instead of comparing every element to every element after it, you maintain a stack of indices whose next-greater value is still unknown, kept in decreasing order of their array values from bottom to top. As you scan forward, if the current value beats the value at the stack's top index, that top index has finally found its answer, so you pop it, record the current value as its next greater element, and repeat the check against the new top — possibly resolving several indices in one step. If the current value doesn't beat the top, you simply push the current index and move on. Any indices left on the stack after the full scan have no next greater element, which you mark with -1 or a sentinel; the amortized cost is O(n) because each index is pushed once and popped at most once across the whole scan, even though the popping loop looks nested.
- O(n) time versus O(n^2) brute force pairwise comparison
- O(n) space for the stack in the worst case
- Each index is pushed and popped at most once (amortized linear)
- Generalizes to next smaller element, circular arrays, and stock span problems
AI Mentor Explanation
A commentator tracking, for each batter's score, the first later batter to beat it keeps a stack of batters whose "who beats me next" question is still unanswered, ordered so the stack only ever holds decreasing scores from bottom to top. When a new batter's score beats the score on top of the stack, that top batter's question is finally answered — pop them off and record the new batter as their answer — and keep popping as long as the new score keeps beating the next one down. If the new score doesn't beat the top, the new batter simply joins the stack to wait their turn. By the end of the innings, whoever remains on the stack was never beaten, so they get no answer, and every batter was pushed and popped at most once, keeping the whole commentary pass linear.
Step-by-Step Explanation
Step 1
Initialize result array and empty stack
Fill result with -1 for every index; the stack will hold indices whose answer is still unresolved.
Step 2
Scan left to right
For each index i, while the stack is non-empty and nums[i] > nums[stack top], pop and set result of the popped index to nums[i].
Step 3
Push the current index
After resolving as many pending indices as possible, push the current index onto the stack.
Step 4
Leftover indices stay -1
Any indices still on the stack after the scan never found a greater element, so their result remains -1.
What Interviewer Expects
- Recognize the monotonic stack pattern instead of proposing O(n^2) brute force
- Explain why the stack is kept in decreasing order
- Justify amortized O(n) despite the inner while loop looking nested
- Extend the idea to circular arrays by conceptually scanning the array twice
Common Mistakes
- Storing values instead of indices on the stack, losing the ability to write results back to the right position
- Not popping in a while loop, missing that one element can resolve multiple stack entries
- Forgetting to initialize unresolved results to -1 (or the problem's sentinel)
- Mishandling the circular array variant by not wrapping the scan or double-scanning correctly
Best Answer (HR Friendly)
“I keep a stack of elements that are still waiting to find something bigger than them, and the stack stays in decreasing order from bottom to top. As I scan the array, any time the current number beats what's on top of the stack, I know I've found that stacked number's answer, so I pop it and record the match, possibly popping several at once. Anything still stuck on the stack at the end just never found a bigger number.”
Code Example
def next_greater_elements(nums):
n = len(nums)
result = [-1] * n
stack = [] # holds indices, values decreasing bottom to top
for i in range(n):
while stack and nums[i] > nums[stack[-1]]:
idx = stack.pop()
result[idx] = nums[i]
stack.append(i)
return resultFollow-up Questions
- How would you solve this for a circular array where the search wraps around?
- How would you adapt this to find the next smaller element instead?
- How does this relate to the daily temperatures / stock span problems?
- What would you change to also return the distance to the next greater element, not just its value?
MCQ Practice
1. What order does the monotonic stack maintain in this problem?
The stack holds indices whose values decrease from bottom to top, so any larger incoming value resolves the top entries first.
2. What is the amortized time complexity of the monotonic stack solution?
Each index is pushed once and popped at most once across the entire scan, giving amortized O(n) despite the inner while loop.
3. What value should be assigned to an index that never finds a next greater element?
Indices remaining on the stack after the full scan never found a larger value, so they are conventionally marked -1.
Flash Cards
What does the monotonic stack store in this problem? — Indices of elements whose next greater element is still unknown, kept in decreasing value order.
When is an index popped from the stack? — When the current element's value is greater than the value at the index on top of the stack.
What is the time complexity? — O(n) amortized, since each index is pushed and popped at most once.
What happens to indices left on the stack at the end? — They have no next greater element, so their result is set to -1.