#503
Next Greater Element II
Medium Monotonic stack, circular
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
The array is circular. For each element, return the next greater element when searching forward (wrapping around), or -1.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: next greater element in a circular array.
Why this works: loop twice; the second lap only answers items still waiting.
Example: [1, 2, 1]
2 answers the first 1second lap: 2 answers the last 1; 2 itself → -1[2, -1, 2]
✦Hints open one at a time
Loop through the array twice (indexes 0..2n−1, using i % n).
Only push indexes during the first pass.
↗Approach
Fill answers with -1. For i in 0..2n−1, let x = nums[i % n]; pop every index whose value is smaller than x and set its answer to x. Push i only when i < n.
</>Solution (Java)
import java.util.*;
class Solution {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
Arrays.fill(ans, -1);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < 2 * n; i++) {
int x = nums[i % n];
while (!stack.isEmpty() && nums[stack.peek()] < x) ans[stack.pop()] = x;
if (i < n) stack.push(i); // second lap only answers, never waits
}
return ans;
}
}!Common mistake
Pushing during the second pass too, which can record wrong answers and wastes work.
Complexity
- Time: O(n).
- Space: O(n).
Topic: Stack & Queue
🎬 Episodes 46–52: video coming soon