Next Greater Element II (LeetCode 503)

The problem

You get an integer array nums that is circular: after the last element you wrap around to the first. For each element, return the first value greater than it that you meet while walking forward (wrapping if needed). If none exists, return -1 for it. Duplicates are allowed.

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

The first 1 sees 2 next. 2 is the maximum, so nothing beats it. The last 1 wraps around, passes the first 1, and meets 2.

How to think about it

Start with brute force. For each index i, walk forward j = i+1, i+2, … using j % n, up to n - 1 steps, and stop at the first bigger value. That is O(n²), and the input can have 10,000 elements or more.

Recall the non-circular version. For a plain array, a decreasing stack of indices solves “next greater” in one pass: every index waits on the stack until a bigger value arrives and pops it. Indices still on the stack at the end have no answer. The only problem with the circular array is that those leftover indices might have an answer earlier in the array, after the wrap.

The key insight: walk the array twice. Imagine the array written out twice, nums + nums. Any element’s next greater (with wrap-around) appears within the next n - 1 positions of that doubled array. So loop i from 0 to 2n - 1 and read nums[i % n]. On the first lap you push indices as normal. On the second lap you only pop: the values there act as “the wrapped part” that can resolve leftovers, but you never push them, since every real index has already been pushed once.

Which pattern is this? Monotonic stack for “next greater element”, plus the standard trick for circular arrays: iterate 2n times with modulo. The tell is “circular” combined with “next greater”.

Approach

1. Let n = len(nums). Create res = [-1] * n and an empty stack st of indices.
2. For i in 0 … 2n - 1:
   • Let x = nums[i % n].
   • While the stack is non-empty and nums[st[-1]] < x, pop the index and set its answer to x.
   • If i < n, push i (first lap only).
3. Anything left on the stack keeps -1. Return res.

Solution

def next_greater_elements_circular(nums):
    n = len(nums); res = [-1]*n; st = []
    for i in range(2*n):
        x = nums[i % n]                    # second lap wraps around
        while st and nums[st[-1]] < x:
            res[st.pop()] = x
        if i < n:                          # push each real index once
            st.append(i)
    return res
# next_greater_elements_circular([1,2,1]) -> [2,-1,2]

Dry run

Index 1 (the maximum) is never popped, so the answer is [2, -1, 2].

Complexity

• Time: O(n). The loop runs 2n times. Each index is pushed once and popped at most once, so the inner loop totals O(n).
• Space: O(n). The result array and the stack.

Edge cases and pitfalls

• The maximum (every copy of it) always gets -1, because nothing is strictly greater anywhere in the circle.
• Duplicates are why you store indices, not values: two equal values at different positions need separate answers.
• Pushing on the second lap too puts indices >= n on the stack, and res[st.pop()] then goes out of range. Push i % n instead and you just redo work. Push only on the first lap.
• All equal values such as [5, 5, 5] give [-1, -1, -1], since you need strictly greater.
• Single element returns [-1].

Related problems

• Next Greater Element I (LeetCode 496): the linear version, with value lookups through a dictionary.
• Daily Temperatures (LeetCode 739): same stack of indices, returning distances.
• Sliding Window Maximum (LeetCode 239): a monotonic structure (a deque) that also drops elements from the front.