Next Greater Element II
Find the next greater element of every value in a circular array with a monotonic stack of indexes and two passes over the array.
Problem Understanding
Next Greater Element II: nums is circular, so after the last element comes the first. For every index, return the first greater value found by walking right and wrapping around, or -1 if there is none.
Example: nums = [1, 2, 1] returns [2, -1, 2]. The last 1 wraps around and finds 2.
The Intuition: The Same Stack, Two Laps
Without the wrap, this is Next Greater Element I: a decreasing monotonic stack of values waiting for something bigger, popped by each larger value.
The wrap adds one idea: walk the array twice. Loop i from 0 to 2n − 1 and read nums[i % n]:
- First lap: pop smaller waiting indexes and write their answers, then push
i. - Second lap: keep popping, but push nothing. The values at the start of the array now act as the "right side" of the values at the end.
- Whatever is still waiting (the maximum, at least) keeps
-1.
Interactive Walkthrough
nums is on top with x = nums[i % n] filled; below it, the stack of waiting indexes and the answer array. Use the Wrap needed preset to see the second lap resolve four indexes at once.
Dry Run Table
Input: nums = [1, 2, 1], n = 3
| i | i % n | x | Popped | Push | Stack |
|---|---|---|---|---|---|
| 0 | 0 | 1 | — | 0 | [0] |
| 1 | 1 | 2 | ans[0] = 2 | 1 | [1] |
| 2 | 2 | 1 | — | 2 | [1, 2] |
| 3 | 0 | 1 | — | no | [1, 2] |
| 4 | 1 | 2 | ans[2] = 2 | no | [1] |
| 5 | 2 | 1 | — | no | [1] |
Index 1 holds the maximum and is never popped. Answer: [2, -1, 2].
The Solution Template
Two laps with i % n, a stack of indexes, and pushes on the first lap only.
Next Greater Element II Code
1var nextGreaterElements = function(nums) {2 const n = nums.length, ans = new Array(n).fill(-1), stack = [];3 for (let i = 0; i < 2 * n; i++) {4 const x = nums[i % n];5 while (stack.length && nums[stack[stack.length - 1]] < x) ans[stack.pop()] = x;6 if (i < n) stack.push(i);7 }8 return ans;9};
Edge Cases & Common Mistakes
- The maximum: nothing is greater, even after wrapping, so it always keeps -1.
- Duplicates: equal is not greater;
[3, 3, 3]returns all -1. Compare with<, not≤. - Storing values on the stack: with duplicates you cannot tell where to write; store indexes.
- Pushing on the second lap: harmless for the answer but doubles the stack; push only when
i < n. - Concatenating nums + nums: works, but
i % ngives the same lap without the extra copy.
Summary
Fill the answer with -1 and loop i from 0 to 2n − 1 over nums[i % n]. A decreasing stack of indexes waits for something bigger; each larger value pops them and writes itself as their answer. Push only on the first lap. O(n) time, O(n) space.
More practice: DSA interview questions with answers · patterns cheat sheet