Next Greater Element II — Circular Array Monotonic Stack

Problem Statement#

Given a circular integer array nums (the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums. The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.

Constraints:

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

Input:  nums = [1,2,1]
Output: [2,-1,2]
Explanation:
1 (index 0) → next greater is 2 (index 1) → 2
2 (index 1) → no greater element found circularly → -1
1 (index 2) → wraps around, finds 2 at index 1 → 2

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

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

Why This Problem Matters#

LC 503 is the circular extension of Next Greater Element I (LC 496) and Daily Temperatures (LC 739). It introduces the critical "process twice" trick for circular arrays — a technique that appears across many competitive programming and FAANG problems.

Key patterns this problem teaches:

1. Circular array handling with modulo — instead of physically duplicating the array (O(n) extra space), use i % n to simulate wrapping.
2. When to push vs when to only resolve — during the second pass (simulated wrap-around), you should not push new pending elements, only resolve existing ones.

The circular monotonic stack pattern appears in: Jump Game VI (LC 1696), Shortest Subarray with Sum at Least K (LC 862), and various contest problems. Understanding why two passes work is essential for FAANG interviews.

The Core Insight#

Why two passes work: In a circular array, an element can look forward up to n positions (wrapping around). If we process the array twice (indices 0 to 2n-1, using i % n), every element has the opportunity to "see" every other element exactly once in its forward direction.

When to stop pushing: During the second pass (i >= n), we only want to resolve pending elements — not push new ones. If we pushed during the second pass, elements from the first pass would have duplicates in the stack.

What's in the stack? Unlike NGE I where we can store values, here we store indices because:

• Elements may not be unique (unlike NGE I).
• We need to know which position to write the answer for.

Monotonic invariant: The stack holds indices of elements (in decreasing temperature order) that are still waiting for their next greater element. When nums[i % n] is greater than nums[stack.top], the top has found its answer.

Visual Dry Run#

Input: nums = [1,2,1], n = 3

We process i from 0 to 5 (2n-1):

Stack [1] still has index 1 → res[1] = -1 (no next greater).

Result: [2,-1,2]

Solution (Optimal)#

# Python — circular monotonic stack, O(n) time and space
def nextGreaterElements(nums: list[int]) -> list[int]:
    n = len(nums)
    res = [-1] * n
    stack = []  # stores indices, monotonically decreasing by nums value
 
    # Process 2n indices to simulate circular wrap-around
    for i in range(2 * n):
        # Resolve pending elements smaller than nums[i % n]
        while stack and nums[stack[-1]] < nums[i % n]:
            idx = stack.pop()
            res[idx] = nums[i % n]
 
        # Only push during the first pass (i < n)
        # During the second pass, we only resolve, not add new pending elements
        if i < n:
            stack.append(i)
 
    return res

// JavaScript — circular monotonic stack, O(n) time and space
function nextGreaterElements(nums) {
    const n = nums.length;
    const res = new Array(n).fill(-1);
    const stack = [];  // indices in monotonically decreasing order of nums value
 
    for (let i = 0; i < 2 * n; i++) {
        const curr = nums[i % n];
 
        // Resolve all pending elements smaller than current
        while (stack.length > 0 && nums[stack[stack.length - 1]] < curr) {
            const idx = stack.pop();
            res[idx] = curr;
        }
 
        // Only push new elements during the first n iterations
        if (i < n) {
            stack.push(i);
        }
    }
 
    return res;
}

Complexity:

Common Mistakes#

1. Pushing elements during the second pass. If you push at i >= n, you create duplicate pending entries for the same positions. Only push when i < n — the second pass is for resolving, not for adding.

2. Using nums[i % n] for the comparison but i for the stack. Since you need to track which original index to assign the answer to, store the actual index i % n (not i) or restrict pushes to i < n and store i. Both are valid; the code above uses i directly since i < n guarantees it equals i % n.

3. Confusing NGE I and NGE II. NGE I has a linear array — no modulo needed. NGE II is circular — use i % n and the two-pass trick. Mixing them up is a common interview mistake.

4. Initializing result with 0 instead of -1. Elements with no next greater element must return -1. Initialize res = [-1] * n so unreached elements default correctly.

5. Not using strict less-than. The next greater (not greater-or-equal) element. Use nums[stack[-1]] < nums[i % n], not <=.

Interview Tips#

• Explain the two-pass insight: "In a circular array, every element may look forward up to n positions. Processing 2n indices with i % n gives each element one full forward view. The modulo wraps around without duplicating the array."
• Explain why you only push during the first pass: "During the second pass, we are giving existing pending elements a chance to see elements they missed. Adding new pending elements in the second pass would create duplicates."
• Compare with NGE I: "The only additions to NGE I are: store indices instead of values (elements may not be unique), loop 2n times, and only push when i < n."

Follow-up Questions#

1. Next Greater Element I (LC 496) — linear array variant without circular wrap.
2. Daily Temperatures (LC 739) — return day differences instead of the next greater values.
3. Previous Greater Element (circular). Process from right to left twice (2n down to 0) with the same stack logic.
4. Circular array with k-step lookahead. Process k*n indices with modulo, not just 2n.
5. What if duplicates are allowed and you need the next strictly greater? Same logic — the strict less-than comparison handles duplicates correctly (equal elements do not resolve each other).

Key Takeaways#

• Two-pass trick for circular arrays: process 2n indices with i % n to give every element one full forward view. This requires O(n) time — not O(n^2) — because each index is pushed and popped at most once.
• Only push during the first pass (i < n): the second pass is purely for resolving existing pending elements, not adding new ones.
• Store indices (not values) in the stack because elements may not be unique and you need to write the answer to a specific position.
• Elements remaining in the stack after both passes have no next greater element → their res entries stay -1.
• The same "process array k times with modulo" trick applies to any circular-array problem that needs forward lookahead.
• This is the direct extension of the monotonic stack from NGE I — if you understand NGE I well, NGE II adds only the modulo and push-restriction.