Next Greater Element II
Find the next greater element in a circular array.
Pattern fit
The monotonic-stack logic stays the same as the non-circular version, but you simulate wraparound by scanning twice.
Key observation
The second pass exists only to resolve elements left unanswered from the first pass.
Target complexity
O(n) / O(n)
How to break down the solution cleanly
The monotonic-stack logic stays the same as the non-circular version, but you simulate wraparound by scanning twice.
The second pass exists only to resolve elements left unanswered from the first pass.
Decide what unresolved property the stack maintains.
Push indices while the monotonic invariant holds.
Reference implementation
Python# Generic pattern template
stack = []
for i, value in enumerate(nums):
while stack and nums[stack[-1]] < value:
prev_index = stack.pop()
# value is the next greater for prev_index
stack.append(i)
Common pitfalls
Pushing indices again in the second pass and duplicating work incorrectly.
Forgetting that the answer for unresolved elements may remain -1.
Common follow-ups
Why is iterating 2n enough?
Which indices should be pushed only once?
Continue with related problems
Build repeatable depth inside the Monotonic Stack cluster before moving on.