Next Greater Element II: Circular Array Stack Pattern

LeetCode 503, Next Greater Element II, is a medium problem that extends the monotonic stack pattern to circular arrays. You are given a circular array, and for each element you need to find the first element to its right that is greater, wrapping around the end of the array if necessary. It is a natural follow-up to Next Greater Element I, and the twist forces you to think about how to simulate circularity without actually building a circular data structure.

The problem

Given a circular integer array nums, return the next greater number for every element. The next greater number of an element x is the first number that is greater than x when traversing the array to the right in a circular fashion. If no such number exists, the answer is -1.

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

For index 0 (value 1), the next greater element going right is 2 at index 1. For index 1 (value 2), you go right through index 2 (value 1) and wrap back to index 0 (value 1), but nothing is greater than 2, so the answer is -1. For index 2 (value 1), you wrap around to index 0 (value 1, not greater), then index 1 (value 2, which is greater), so the answer is 2.

The brute force

For each element, scan to the right up to n-1 positions (wrapping around with modulo) until you find something greater.

def next_greater_elements_brute(nums):
    n = len(nums)
    result = [-1] * n
    for i in range(n):
        for j in range(1, n):
            if nums[(i + j) % n] > nums[i]:
                result[i] = nums[(i + j) % n]
                break
    return result

For each of n elements, you potentially scan n-1 others. That is O(n^2) in the worst case, for example when the array is sorted in decreasing order.

The key insight

The standard monotonic stack approach processes the array left to right in a single pass. For a circular array, a single pass is not enough because elements near the end might have their next greater element near the beginning.

The trick is to traverse the array twice. By iterating from index 0 to 2n-1 and using i % n to get the actual index, you simulate one full wrap around the array. During the second pass, elements that were stuck on the stack from the first pass finally get a chance to find their next greater element from the beginning of the array.

You still use a monotonic decreasing stack of indices. When the current value is greater than the value at the top index, you pop and record the answer. The only difference from the non-circular version is that you loop to 2n instead of n, and you only push indices during the first pass (or equivalently, always push i % n but only write results when the slot has not been filled yet).

Step-by-step walkthrough

Let's trace through nums = [1, 2, 3, 2, 1]. We iterate from i=0 to i=9 (that is, 2n-1 where n=5). At each step you will see the array, the current position, the stack of indices, and the result array being filled in.

A few observations from the walkthrough:

• The second pass resolves elements that wrap around. Index 4 (value 1) gets resolved during the second pass when we encounter value 2 at index 1 again.
• Index 3 (value 2) also resolves during the second pass when we encounter value 3 at index 2 on the wrap-around.
• Index 2 (value 3) is the maximum. It never gets popped because no element in the array is greater. Its result stays -1.
• Each index is pushed at most once and popped at most once. Even though we loop 2n times, the total work is still O(n).

The code

def next_greater_elements(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

Let's break this down line by line:

1. result = [-1] * n initializes every answer to -1. If an element never gets popped, it means nothing greater exists.
2. stack = [] holds indices in a monotonic decreasing order by their corresponding values.
3. We loop from 0 to 2n-1. The variable idx = i % n gives the actual position in the array.
4. The while loop pops all stack indices whose values are smaller than nums[idx]. For each popped index, the current value is its next greater element.
5. if i < n: stack.append(idx) ensures we only push each index once (during the first pass). The second pass is purely for resolving leftover elements.
6. The function returns result, where each position holds either the next greater element or -1.

Complexity analysis

Time: O(n). Even though the loop runs 2n iterations, each of the n indices is pushed onto the stack exactly once and popped at most once. The total number of push and pop operations is at most 2n, making the amortized cost O(n).

Space: O(n). The stack holds at most n indices, and the result array is size n.

Building blocks

The core pattern is the same monotonic stack pop loop from Next Greater Element I:

while stack and nums[current] > nums[stack[-1]]:
    popped = stack.pop()
    result[popped] = nums[current]
stack.append(current)

The circular extension adds one idea: loop twice to simulate wrapping. This same doubled-traversal trick works whenever you need to handle circularity in array problems. You will see it again in problems like Circular Buffer queries, certain sliding window problems on circular arrays, and anywhere the "next" relationship can wrap around.

The key differences from the non-circular version:

• Store indices instead of values (you need to know where to write the answer)
• Loop to 2n instead of n (simulates the wrap-around)
• Guard the push with if i < n so each index appears on the stack at most once

Edge cases

Before submitting, verify your solution handles:

• All elements the same like [3, 3, 3]: nothing is strictly greater, so every answer is -1. The stack fills up during the first pass and nothing gets popped during the second pass.
• Strictly increasing like [1, 2, 3, 4]: every element except the maximum has a next greater element to its right. The maximum wraps around but finds nothing greater, returning -1.
• Strictly decreasing like [4, 3, 2, 1]: in a non-circular version every answer would be -1. But here, the first element 4 has no greater element (it is the max), while elements 3, 2, and 1 all find 4 by wrapping around.
• Single element like [5]: the answer is [-1]. Wrapping around just finds the same element, which is not strictly greater.
• Two elements like [1, 2]: answer is [2, -1]. Value 1 finds 2, and value 2 wraps but finds only 1.
• Maximum in the middle like [1, 5, 2]: the maximum element always returns -1. Elements on both sides of it can find their answers in a single left-to-right pass or via the wrap.

From understanding to recall

You now understand how the doubled-traversal trick extends the monotonic stack to circular arrays. The code is compact: just a few lines different from the non-circular version. But under interview pressure, it is easy to forget whether you loop to 2n or 2n-1, whether you push during both passes or just the first, and whether you need a separate check before writing the result.

Spaced repetition cements these details. After writing the solution from scratch a few times at increasing intervals, you will not need to re-derive the approach. You will know instantly that circular means "loop to 2n, push only when i is less than n, store indices, use modulo." That kind of automatic recall is what separates quick solves from slow re-derivations.

Related posts

• Next Greater Element I - the non-circular predecessor
• Daily Temperatures - same stack pattern, asks for distances instead of values
• Stack Patterns - overview of monotonic stack and other stack techniques

CodeBricks takes the circular monotonic stack pattern and drills it as a standalone building block. You write the doubled loop, the index-based stack, and the conditional push from memory. After a few repetitions, applying this pattern to any circular array problem becomes second nature.