Next Greater Element II

Next Greater Element II

What is this problem about?

The Next Greater Element II problem gives you a circular array and asks for the next greater element for every position — wrapping around if needed. If no greater element exists in the entire array, return -1 for that position. This Next Greater Element II coding problem extends the monotonic stack to handle circular arrays.

Why is this asked in interviews?

Apple, Goldman Sachs, Microsoft, Meta, Amazon, Google, and Bloomberg ask this to test whether candidates can adapt the monotonic stack to circular arrays. The array, monotonic stack, and stack interview pattern is directly demonstrated, and the circular extension — doubling the array conceptually — is a key technique.

Algorithmic pattern used

Monotonic stack with doubled iteration. Process the array twice (simulate circularity by iterating 2n times using i % n). In the first pass, build the stack. In the second pass, resolve remaining stack entries. Use a decreasing stack storing indices (not values) to correctly track positions in the result array.

Example explanation

Array: [3, 1, 2, 4]. Result: [-1, 2, 4, -1] (let's verify).

• Index 0 (3): push.
• Index 1 (1): 1 < 3, push. Stack: [0,1].
• Index 2 (2): 2 > arr[1]=1 → pop 1, result[1]=2. 2 < arr[0]=3 → push. Stack: [0,2].
• Index 3 (4): 4 > arr[2]=2 → pop 2, result[2]=4. 4 > arr[0]=3 → pop 0, result[0]=4. Stack: [3].
• Second pass: index 4%4=0 (3): 3 < arr[3]=4... Wait, stack top is index 3 (4). 3 < 4 → pop, result[3]=3? No... result[3]=-1 since 4 is max. Stack: []. Final: result = [4, 2, 4, -1]. Hmm, result[0]=4 since circular 4 > 3 ✓.

Common mistakes candidates make

• Not iterating 2n times for the circular pass (missing wrap-around).
• Using i directly instead of i % n when accessing array values.
• Storing values instead of indices in the stack (need index to update result array).
• Not leaving elements in the stack unresolved after 2n passes (they get -1).

Interview preparation tip

Circular array problems always use the "double the array" or "iterate 2n with modulo" trick. For circular next-greater, iterate 2n times, use i % n for array access, and push indices when not resolving the stack. After 2n iterations, remaining stack entries have no next greater (-1). Practice this circular extension for both next-greater and next-smaller variants on circular arrays.