Next Greater Element II
Medium · Stack & Strings · Array · Stack · Monotonic Stack
Problem
You are given a circular integer array nums: the element after nums[len(nums) - 1] is nums[0].
For each element, find its next greater number: the first value strictly larger than it that you meet walking forward from it, wrapping around to the start if needed. If there is none, use -1. Return the answers as an array aligned with nums.
Examples
Input: nums = [3,8,4,1,2] Output: [8,-1,8,2,3]
The trailing 2 wraps around and finds 3. 8 is the maximum, so it gets -1.
Input: nums = [5,5,5] Output: [-1,-1,-1]
No value is strictly greater than 5.
Input: nums = [1,2,1] Output: [2,-1,2]
The last 1 wraps around past the first 1 to reach 2.
Constraints
- 1 <= len(nums) <= 10^4
- -10^9 <= nums[i] <= 10^9
Approaches
- Baseline: walk forward from every element — time O(n²), space O(1) beyond the result
Follow-up
Return the distance (number of steps forward) to the next greater value instead of the value itself. Then do the same for the next smaller value. Both are one-line changes to the stack loop.
Related problems
Start free on Cariara · Coding problems · System design studio
