Next Greater Element II
Problem (restated)
Circular array: for each index i, find the next strictly greater element to the right, wrapping around once. If none exists, -1.
Intuition
Same decreasing stack as linear next-greater, but walk the array twice (2n steps with i % n) so wrap-around candidates can resolve earlier indices.
Approaches
Circular next-greater (2n scan)
Tested onlyIdea. Indices stack, decreasing by value. On each step pop while current is greater and write ans[popped] = nums[i]. Only push during the first pass so each index is pending at most once.
Walkthrough. [1,2,1] → for index 2 (value 1), wrapping finds 2 → [2,-1,2].
Trade-offs. Still O(n): each index pushed once and popped at most once. Pushing on the second pass is unnecessary and can corrupt answers if not careful.
export function nextGreaterElements(nums: number[]): number[] {
const n = nums.length;
const ans = new Array<number>(n).fill(-1);
const stack: number[] = [];
for (let k = 0; k < 2 * n; k++) {
const i = k % n;
while (stack.length && nums[i]! > nums[stack[stack.length - 1]!]!) {
ans[stack.pop()!] = nums[i]!;
}
if (k < n) stack.push(i);
}
return ans;
}
export function nextGreaterElements(nums: number[]): number[] {
const n = nums.length;
const ans = new Array<number>(n).fill(-1);
const stack: number[] = [];
for (let k = 0; k < 2 * n; k++) {
const i = k % n;
while (stack.length && nums[i]! > nums[stack[stack.length - 1]!]!) {
ans[stack.pop()!] = nums[i]!;
}
if (k < n) stack.push(i);
}
return ans;
}
Template connection
Next-greater template + circular virtual length. Pair with NGE I (496) and Daily Temperatures (739).
Reflection
- Which pattern gave this away within 90 seconds?
- What changed from the standard template?
- What would break the current solution?