Next Greater Element II — Circular Array with Monotonic Stack (LeetCode 503)

Next Greater Element II (LeetCode 503) extends the classic next-greater-element problem to circular arrays. After the last element, you wrap around to the beginning. The key trick: iterate through the array twice using modular indexing.

The Problem

Given a circular integer array, find the next greater number for every element. The “next” search wraps around.

Input:  [1, 2, 1]
Output: [2, -1, 2]

Explanation:
  1 → next greater is 2
  2 → wraps around: 1, 1 — no greater → -1
  1 → wraps around: 1, 2 — next greater is 2

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

  1 → 2
  2 → 3
  3 → 4
  4 → wraps: 3, 1, 2, 3 — no greater → -1
  3 → wraps: 1, 2, 3, 4 → 4

The Circular Challenge

In the non-circular version, we process each element once and look only to the right. With circular arrays, the search continues past the end and wraps to the beginning.

The insight: iterate through the array twice. On the second pass, earlier elements can serve as “next greater” for elements near the end.

Approach: Monotonic Stack + Double Iteration

def nextGreaterElements(nums):
    """
    Next Greater Element II — circular array.
    Time: O(n), Space: O(n)
    """
    n = len(nums)
    result = [-1] * n
    stack = []  # stores indices

    # Iterate through array twice (2n iterations)
    for i in range(2 * n):
        idx = i % n

        # Pop elements smaller than current
        while stack and nums[idx] > nums[stack[-1]]:
            result[stack.pop()] = nums[idx]

        # Only push during the first pass
        if i < n:
            stack.append(idx)

    return result

Why Iterate Twice?

Consider [5, 4, 3, 2, 1]:

• On the first pass (indices 0-4): no element finds a next greater (everything is decreasing)
• On the second pass (indices 5-9, mapping to 0-4): element at index 4 (value 1) sees value 5 at index 0, element at index 3 (value 2) sees value 5, etc.

By processing 2n elements but only pushing indices in the first n, we simulate the circular lookup without actually duplicating the array.

Step-by-Step Trace

nums = [1, 2, 3, 4, 3]
n = 5, result = [-1, -1, -1, -1, -1]

First pass (i = 0 to 4):
─────────────────────────
i=0, idx=0, nums[0]=1
  stack empty → push 0
  stack = [0]

i=1, idx=1, nums[1]=2
  2 > nums[0]=1 → result[0]=2, pop 0
  stack empty → stop
  push 1
  stack = [1]

i=2, idx=2, nums[2]=3
  3 > nums[1]=2 → result[1]=3, pop 1
  push 2
  stack = [2]

i=3, idx=3, nums[3]=4
  4 > nums[2]=3 → result[2]=4, pop 2
  push 3
  stack = [3]

i=4, idx=4, nums[4]=3
  3 < nums[3]=4 → no pop
  push 4
  stack = [3, 4]

Second pass (i = 5 to 9):
─────────────────────────
i=5, idx=0, nums[0]=1
  1 < nums[4]=3 → no pop
  (don't push, i >= n)

i=6, idx=1, nums[1]=2
  2 < nums[4]=3 → no pop

i=7, idx=2, nums[2]=3
  3 == nums[4]=3 → no pop (not strictly greater)

i=8, idx=3, nums[3]=4
  4 > nums[4]=3 → result[4]=4, pop 4
  4 == nums[3]=4 → no pop
  stack = [3]

i=9, idx=4, nums[4]=3
  3 < nums[3]=4 → no pop

Final result = [2, 3, 4, -1, 4]

Alternative: Actually Duplicate the Array

A conceptually simpler (but slightly less space-efficient) approach:

def nextGreaterElements_dup(nums):
    """Double the array explicitly."""
    n = len(nums)
    doubled = nums + nums  # [1,2,3,4,3,1,2,3,4,3]
    result = [-1] * (2 * n)
    stack = []

    for i in range(2 * n):
        while stack and doubled[i] > doubled[stack[-1]]:
            result[stack.pop()] = doubled[i]
        stack.append(i)

    return result[:n]

This uses O(n) extra space for the doubled array. The modular approach avoids this.

Non-Circular vs Circular Comparison

# Non-circular (LC 496/739): iterate once
def next_greater_linear(nums):
    n = len(nums)
    result = [-1] * n
    stack = []
    for i in range(n):
        while stack and nums[i] > nums[stack[-1]]:
            result[stack.pop()] = nums[i]
        stack.append(i)
    return result

# Circular (LC 503): iterate twice
def next_greater_circular(nums):
    n = len(nums)
    result = [-1] * n
    stack = []
    for i in range(2 * n):
        idx = i % n
        while stack and nums[idx] > nums[stack[-1]]:
            result[stack.pop()] = nums[idx]
        if i < n:
            stack.append(idx)
    return result

The only differences:

1. Loop runs 2n times instead of n
2. Use i % n for the actual index
3. Only push during the first pass (i < n)

Complexity Analysis

Metric	Value
Time	O(n) — each index pushed once, popped at most once, over 2n iterations
Space	O(n) — stack and result array

Even though we iterate 2n times, each element enters and leaves the stack at most once, so the total work is O(n).

Edge Cases

# Single element — wraps to itself, no greater
assert nextGreaterElements([5]) == [-1]

# All same elements
assert nextGreaterElements([3, 3, 3]) == [-1, -1, -1]

# Strictly increasing — last has no greater, rest are obvious
assert nextGreaterElements([1, 2, 3]) == [2, 3, -1]

# Strictly decreasing — each wraps around to find a greater
assert nextGreaterElements([3, 2, 1]) == [-1, 3, 3]

# Two elements
assert nextGreaterElements([2, 1]) == [-1, 2]

When to Use This Pattern

Use the double-iteration monotonic stack when:

• The problem involves a circular array with next/previous greater/smaller
• You need to “wrap around” the end to the beginning
• Any problem that uses monotonic stack on a linear array but with circular semantics

The same trick works for:

• Next smaller element in circular array
• Previous greater element in circular array
• Any variant where the search should wrap

Common Mistakes

1. Only iterating once — misses wraparound cases
2. Pushing during the second pass — causes duplicates in the stack
3. Forgetting i % n — index out of bounds on the second pass
4. Using >= instead of > — “greater” means strictly greater

Related Problems

Problem	Key Difference
Next Greater Element I (LC 496)	Two arrays, no circular
Daily Temperatures (LC 739)	“How many days until warmer”
Largest Rectangle in Histogram (LC 84)	Next smaller from both sides
Circular Array Loop (LC 457)	Cycle detection, not next greater
Stock Span (LC 901)	Previous greater element

Key Takeaways

• The circular array trick: iterate 2n times with i % n indexing
• Only push indices during the first n iterations to avoid duplicates
• The monotonic stack invariant is the same as the non-circular version
• Each element is pushed once and popped at most once: O(n) total
• This pattern extends naturally to any circular monotonic stack problem