MediumNeetCode150ArrayStackMonotonic StackCircular Array
Next Greater Element II
Find next greater in circular array.
Examples
Input
nums = [1,2,1]
Output
[2,-1,2]
1->2, 2->-1, 1->2 (circular).
Constraints
- •
1 <= nums.length <= 10^4 - •
-10^9 <= nums[i] <= 10^9
Approaches
For each, scan ahead circularly.
CodeT: O(n^2) | S: O(1)
Traverse array twice.
CodeT: O(n) | S: O(n) stack + output
Same approach.
CodeT: O(n) | S: O(n)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(n^2) | O(1) | For each, scan ahead circularly. |
| Monotonic Stack | O(n) | O(n) stack + output | Traverse array twice. |
| Stack Optimized | O(n) | O(n) | Same approach. |
Brute Force
T: O(n^2)S: O(1)
For each, scan ahead circularly.
Monotonic Stack
T: O(n)S: O(n) stack + output
Traverse array twice.
Stack Optimized
T: O(n)S: O(n)
Same approach.
Common Mistakes
Not handling circular nature
Off-by-one in traversal
Wrong stack operations