Next Greater Element II — Circular Array Monotonic Stack

Problem Statement#

Given a circular integer array nums (where the next element of nums[n-1] is nums[0]), return the next greater number for every element. The next greater number is the first greater number found traversing circularly. If it does not exist, return -1.

Constraints:

• 1 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9

Input:  nums = [1, 2, 1]
Output: [2, -1, 2]
Explanation: For 1 at index 2: wraps around, finds 2 at index 0.

Input:  nums = [1, 2, 3, 4, 3]
Output: [2, 3, 4, -1, 4]

Why This Problem Matters#

Next Greater Element II is the direct extension of Next Greater Element I (LC 496) to a circular array. It is frequently asked at Amazon, Google, and Microsoft as a follow-up to the base NGE problem. Interviewers want to see if you can modify the double-pass trick (iterate 2n indices, use modular arithmetic) without changing the core stack logic.

The circular structure appears in many real problems: finding the next warmer day in a year that wraps around, the next available server in a round-robin pool, or the next event in a circular calendar. Understanding this adaptation unlocks an entire class of circular array problems.

The key challenge: candidates who have only memorized the left-to-right NGE pattern struggle to adapt it. Candidates who understand the invariant adapt in seconds.

The Core Insight#

The standard NGE algorithm processes elements left to right, maintaining a decreasing stack. For a linear array, a single pass suffices.

For a circular array, an element near the end might have its next greater element at the beginning (wrap-around). The elegant solution: iterate twice (indices 0 to 2n-1), mapping index i to i % n. On the second pass, elements at the beginning serve as potential "next greater" for elements near the end.

The stack stores original indices (0 to n-1). Push only during the first pass (i < n). During the second pass, only pop — never push new indices. This ensures indices in the result array are valid.

After two full passes, every element has either found its next greater or stays at -1 (the maximum element in the array).

Visual Dry Run#

nums = [1, 2, 1], res = [-1, -1, -1]

Result: [2, -1, 2].

Solution (Optimal)#

class Solution:
    def nextGreaterElements(self, nums: list[int]) -> list[int]:
        n = len(nums)
        res = [-1] * n
        stack = []
 
        for i in range(2 * n):
            while stack and nums[stack[-1]] < nums[i % n]:
                res[stack.pop()] = nums[i % n]
 
            if i < n:
                stack.append(i)
 
        return res

var nextGreaterElements = function(nums) {
    const n = nums.length;
    const res = new Array(n).fill(-1);
    const stack = [];
 
    for (let i = 0; i < 2 * n; i++) {
        while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i % n]) {
            res[stack.pop()] = nums[i % n];
        }
 
        if (i < n) {
            stack.push(i);
        }
    }
 
    return res;
};

Time: O(n) — each index is pushed and popped at most once Space: O(n) — stack holds at most n indices

Common Mistakes#

• Pushing indices on the second pass — only push when i < n; pushing on the second pass adds duplicate indices and corrupts the result
• Using values instead of indices in the stack — the stack must store indices so you can write res[popped_index]; values prevent this mapping
• Forgetting i % n for value lookup — when i ranges from 0 to 2n-1, always access nums[i % n]; without modulo you get index out of bounds
• Not initializing res to -1 — elements remaining in the stack after both passes have no next greater element; initialization handles this automatically
• Using <= for the pop condition — pop when nums[stack[-1]] < nums[i % n] (strictly less); equal elements do not resolve each other

Interview Tips#

• Explain the double-pass trick clearly: "I iterate 2n times using i % n to index into the array. On the first pass (i < n), I push indices. On the second pass, I only pop — this handles the wrap-around where elements near the end can have their NGE at the beginning."
• If asked "why does two passes suffice?": "After one full rotation, every element has had the opportunity to see all other elements as potential next-greater candidates. Elements not resolved after two passes have no next greater element in the array."
• Anticipate the follow-up: "Can you solve this in O(1) space?" No — the stack is necessary to hold pending indices. Prove this by noting the maximum element must wait through the entire array.

Follow-up Questions#

• What if you want the previous greater element in a circular array? Scan right to left (or equivalently, iterate 2n times right to left) with a decreasing stack.
• What if you need the NGE only within a sliding window of size k? Use a monotonic deque (sliding window maximum variant) instead of a simple stack.
• What is the space complexity if the array is sorted in strictly increasing order? All n elements are pushed to the stack and none are popped during the first pass. Stack grows to size n. Space: O(n).
• What if all elements are equal? No element is strictly greater than another. All results stay -1. No pops occur during either pass.

Key Takeaways#

• Iterate 2 * n times using i % n to simulate circular access — this handles wrap-around without physically duplicating the array.
• Push indices only during the first pass (i < n); during the second pass, only pop to resolve pending elements.
• The stack stores original indices (0 to n-1), not values — this enables writing to res[popped_index].
• Initialize res to -1 so unresolved elements (the maximum element in the array) are handled automatically.
• Use strict < for the pop condition — equal elements do not resolve each other.
• The maximum element in the array will never be resolved and always returns -1 — this is correct behavior.
• This double-pass pattern generalizes to any "find NGE in a circular sequence" problem and is the standard approach for circular array monotonic stack problems.