Next Greater Element II: The Circular Monotonic Stack
Next Greater Element II (LeetCode 503) gives a circular array and asks, for each element, the first larger value you meet walking forward and wrapping around. Brute force is O(n^2); the interviewer wants O(n).
The stack idea
Keep a stack of indices whose answer is still unknown. Values on the stack are decreasing from bottom to top. When a new value is larger than the value at the top index, that new value is the answer for the top index, so pop and record it. Keep popping while that holds, then push the current index.
Handling the wrap
Loop i from 0 to 2n - 1 and read nums[i % n]. The second pass lets elements near the end find a larger value near the start. Only push indices during the first pass, because pushing in the second pass would just repeat work.
def nextGreaterElements(nums):
n = len(nums)
res = [-1] * n
st = []
for i in range(2 * n):
x = nums[i % n]
while st and nums[st[-1]] < x:
res[st.pop()] = x
if i < n:
st.append(i)
return res
Why it is linear
Each index is pushed once and popped at most once, so the total work is O(n) even though there is a nested while loop. Say this out loud; it is the part interviewers listen for.
Common slips
Using values instead of indices on the stack, which makes duplicates impossible to resolve.
Using <= instead of <, which pops equal values that have no greater element yet.
Forgetting that the maximum element keeps -1.
Disclosure: I work on AI coding interview assistant, a tool that helps candidates practice explaining patterns like this one under time pressure.
Comments