DSA problem
Next Greater Element II
Given a circular integer array nums, return the next greater element for every element in nums. The next greater element of nums[i] is the first element to its right that is strictly greater than nums[i], where indices wrap around — meaning that after the last index we continue from index 0. If no such element exists for some nums[i], the answer for that position is -1.
The non-circular version of this problem is the canonical monotonic-stack template: iterate left-to-right with a decreasing stack of indices, and whenever the current value exceeds the value at the top of the stack, the top has just found its answer. Circularity adds a small twist: an element near the end of the array might find its next greater value by wrapping around to the beginning.
A clean way to handle wraparound is to "double" the array: conceptually iterate the indices 0, 1, …, 2n - 1, using i % n whenever we actually index into nums. We push real indices in [0, n) onto the stack, but during the second pass we only pop — we never push duplicates. That way, each original index appears on the stack at most once, and after the full pass, indices still on the stack genuinely have no next greater element.
The total work is O(n) because we make 2n iterations and each index can be pushed once and popped once. The result vector starts initialised to -1 so that any index never popped retains the correct "no next greater" answer.
Examples
nums = [1,2,1][2,-1,2]nums = [1,2,3,4,3][2,3,4,-1,4]nums = [5,4,3,2,1][-1,5,5,5,5]Constraints
- 1 <= nums.length <= 10^4
- -10^9 <= nums[i] <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.