Algorithm

Next Greater Element II

Monotonic Stack Pattern

Next Greater Element II

Given a circular integer array nums (i.e., 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.

CONSTRAINTS
  • 1 <= nums.length <= 10⁴
  • -10⁹ <= nums[i] <= 10⁹
EXAMPLE 1
Input: nums = [1,2,1]
Output: [2,-1,2]
1's next greater is 2. 2 is the maximum. The second 1 wraps around to find index 1 (value 2).
EXAMPLE 2
Input: nums = [5,4,3,2,1]
Output: [-1,5,5,5,5]
5 has no greater neighbor. All other values wrap around to find 5.
Do we push elements during the second pass?
No. All elements are pushed during the first pass (i < N). The second pass is only used as a chance for those elements to find a 'Next Greater' neighbor from the start of the array.
Can we use this for 'Next Smaller'?
Absolutely. Just flip the comparison logic (current_val < nums[stack.peek()]) and maintain an Increasing Stack instead.

Before diving into this circular version, it is highly recommended to first understand the linear Next Greater Element I logic, where we use a Monotonic Stack as a Waiting Room for numbers.

Standard search ends at the last index. But in a Circular Array, the end of the line wraps back to the beginning. If an element near the end hasn't found its "Next Greater" neighbor yet, it deserves a second chance to look at the numbers at the start of the array.

Think of it as a Circular Marathon. Every runner (number) gets two laps to find someone faster than them. If they still haven't found anyone after two laps, they are officially the fastest in their circle.

The Second Lap

Instead of physically doubling the array (which wastes memory), we mentally simulate two laps using the Modulo Operator (%).
1. The Setup: We run a loop from 0 to 2*N - 1.
2. The Modulo Trick: We use "i % N" to find the real index in the original array. This allows us to treat the sequence [1, 2, 3] as [1, 2, 3, 1, 2, 3] seamlessly.
3. The Rules:
- Resolving: Every element we see acts as a "challenger" to those in the stack. We pop and resolve them exactly like in the linear version.
- Pushing: We ONLY push elements into the stack during the First Lap (i < N). During the second lap, everyone has already had their chance to be a waiter; they are only there to resolve the stragglers left over from the first lap.

Code Blueprint
text
stack = []
results = [-1] * N

// Run for two laps (2 * N)
FOR i from 0 to (2 * N) - 1:
    current_val = nums[i % N]
    
    // Standard Monotonic Resolution
    WHILE stack is NOT empty AND current_val > nums[stack.PEEK()]:
        resolved_index = stack.POP()
        results[resolved_index] = current_val
    
    // Only push during the first lap
    IF i < N:
        stack.PUSH(i)

RETURN results
Worked Example:[1, 2, 1]
0
1
i = 0
1
2
2
1
First pass. Index 0 (val 1): Push index 0. Stack = [0].
0
1
1
2
i = 1 (NGE)
2
1
Index 1 (val 2): 2 > 1. Pop index 0, set ans[0] = 2. Push index 1. Stack = [1].
0
1
1
2
2
1
i = 2
Index 2 (val 1): 1 < 2. Push index 2. Stack = [1, 2].
0
1
i = 3 (circular 0)
1
2
2
1
Second pass (circular loop). Index 3 (val 1): 1 is not > 1 (stack top). Stack remains [1, 2].
0
1
1
2
i = 4 (circular 1)
2
1
Index 4 (val 2): 2 > 1 (value at index 2). Pop index 2, set ans[2] = 2. Stack = [1]. Loop completes. ans[1] remains -1. Result: [2, -1, 2].
Interactive Strategy Visualization
CIRCULAR TRAVERSAL ENGINE

Next Greater Element II Strategy

Pass 1: Initial Scan
1
2
1
Stack
Next Greater
[0]: 1 →-
[1]: 2 →-
[2]: 1 →-

Mental Model

  • Circular Illusion: Iterate `2N` times with `% N` to wrap indices back.
  • Doubling Search: Pass 1 fills the stack with pending candidates; Pass 2 checks if start elements can satisfy them.
LOGICSTEP 1/8
Process circular [1, 2, 1]
HINT

Virtual Doubling

You don't need to copy the array. Just iterate `2 * N` times and use `i % N` to wrap indices back to the start. The logic is identical to the linear version!

O(N²) Brute Force
→
O(N) Double-Pass Monotonic Stack