For each number find the next greater element to its right, or -1, using a monotonic stack in O(n) instead of an O(n²) scan. Interactive Python tests.
The problem
For every element, return the first element to its right that is strictly greater, or -1 if none exists.
Examples
Example 1
Input
next_greater([4, 5, 2, 10, 8])
Expected output
[5, 10, 10, -1, -1]
Example 2
Input
next_greater([3, 2, 1])
Expected output
[-1, -1, -1]
+ 3 hidden tests on Submit — equal is not greater.
Edge cases to ask about
- Strictly decreasing input
- Equal values
- Empty
Hints
0/3How an interviewer scores this
0/9Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.
Complexity Lab
What does this cost as n grows?
Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and measure your code against the optimal one at growing input sizes.
Pick both to reveal the answer.
Measure it
Runs the function on inputs of size 250 up to 16,000 and records the time and peak memory. Slow solutions stop early — a short curve is itself the answer.
From brute force to optimal
The progression an interviewer wants to hear, one step at a time.
| Approach | Time | Space | Idea |
|---|---|---|---|
| Scan right from each element | O(n²) | O(1) | |
| bestMonotonic decreasing stack | O(n) | O(n) | Indices wait on the stack until a bigger value resolves them. |
Walkthrough of the optimal approach (try it yourself first)
Keep a stack of indices whose answer is still unknown; their values are decreasing from bottom to top. When a new value x is bigger than the value at the top, it is that index's answer — pop and record, and repeat. Then push the current index.
Each index is pushed and popped at most once, so despite the nested while the total work is O(n).
Complexity: O(n) time, O(n) space. Each index is pushed once and popped at most once, so the inner while loop does n pops in total.
Reveal the reference solution
def next_greater(nums): result = [-1] * len(nums) stack = [] # indices still waiting for a greater value for i, x in enumerate(nums): while stack and nums[stack[-1]] < x: result[stack.pop()] = x stack.append(i) return result
The brute force, for comparison
def next_greater(nums): out = [] for i in range(len(nums)): nxt = -1 for j in range(i + 1, len(nums)): if nums[j] > nums[i]: nxt = nums[j] break out.append(nxt) return out
Follow-ups interviewers ask
- Circular array.
- Daily temperatures: return how many days until a warmer one.
Frequently asked interview questions
Core interview concepts, complexities, and follow-ups scored by hiring teams.
What is the time complexity of Next Greater Element (Monotonic Stack) in Python?
The optimal solution runs in O(n) time and O(n) auxiliary space. Each index is pushed once and popped at most once, so the inner while loop does n pops in total.
What is the brute-force approach, and how do you optimise it?
Scan right from each element: O(n²) time, O(1) space. Monotonic decreasing stack: O(n) time, O(n) space. Indices wait on the stack until a bigger value resolves them.
What follow-up questions do interviewers ask about Next Greater Element (Monotonic Stack)?
Circular array. Daily temperatures: return how many days until a warmer one.