Next Greater Element II

The plain "next greater element" is the monotonic template from the core lesson. This version adds a twist that interviewers like: the list is circular, so after the last element you continue from the first. The last elements, which usually have no answer, may now find one near the start.

The fix is a standard trick worth knowing by name — walk the list twice — and one guard that separates careful candidates from the rest.

The problem

You are given a circular list of integers: the element after the last one is the first one. For each element, return the first value bigger than it that you meet when moving forward (wrapping around if needed). If there is none, return -1.

• [1, 5, 3, 4, 2] → [5, -1, 4, 5, 5]. The 4 finds nothing to its right, wraps around, passes 1, and meets 5. The 5 is the maximum, so nothing is bigger.
• [3, 3, 3] → [-1, -1, -1]. Equal is not bigger.

Constraints: 1 ≤ n ≤ 10⁴, values between -10⁹ and 10⁹.

Clarifying questions

• Can values repeat? Yes. "Bigger" means strictly bigger.
• How far can we wrap? At most once around: after n - 1 steps you are back at yourself.
• Values or indices in the answer? Values.
• What for the maximum? -1, and every copy of the maximum gets -1.

Approach 1: the simple way

For each index, walk forward up to n - 1 steps, wrapping with % n, and stop at the first bigger value.

1def next_greater_circular_brute(nums: list[int]) -> list[int]:2    """For each index, walk up to n - 1 steps around the circle: O(n^2)."""3    n = len(nums)4    answer = [-1] * n5    for i in range(n):6        for step in range(1, n):7            candidate = nums[(i + step) % n]8            if candidate > nums[i]:9                answer[i] = candidate10                break11    return answer

Time: O(n²). Space: O(1) beyond the answer.

If many values are equal to the maximum — or all are equal — every inner loop runs to the end. At 10⁴ elements that is 10⁸ steps, which takes ten seconds or more in Python. And the waste is the same as in Daily Temperatures: each scan rereads values that earlier scans already compared.

The key insight

A circular list behaves like the list followed by a copy of itself: [1, 5, 3, 4, 2] becomes [1, 5, 3, 4, 2, 1, 5, 3, 4, 2]. Every element's circular "next greater" is its ordinary next greater in the doubled list, because the doubled list shows each element everything that comes after it, all the way round.

You do not need to build the doubled list. Loop step from 0 to 2n - 1 and read nums[step % n]. Then run the normal next-greater stack from the core lesson.

Why are two laps enough, and not three? Element i needs to see the n - 1 elements after it, going round the circle. In the doubled list, those are exactly positions i + 1 to i + n - 1, and every one of them is inside the first 2n positions. A third lap would only show elements that the element has already seen.

Why does the stack still work across the join between the two laps? Because the stack does not care where values come from. At the end of the first lap it holds the elements that found nothing bigger to their right — in decreasing order, exactly as in the plain version. The second lap simply feeds them more values, starting from index 0, and each one that is bigger than the top answers it.

One guard matters: push indices only during the first lap. The second lap is there only to answer elements left waiting from the first lap. Each element needs to wait only once; an index pushed on the second lap would wait for a third lap that never comes.

Approach 2: two laps, one stack

1def next_greater_circular(nums: list[int]) -> list[int]:2    """Next greater value for each index when the array wraps around."""3    n = len(nums)4    answer = [-1] * n5    stack: list[int] = []                        # indices waiting; values decrease upward6    for step in range(2 * n):                    # walk the array twice7        i = step % n8        while stack and nums[stack[-1]] < nums[i]:9            answer[stack.pop()] = nums[i]10        if step < n:                             # only the first lap adds waiting indices11            stack.append(i)12    return answer

Dry run on [1, 5, 3, 4, 2]:

At the end of the first lap, indices 1, 3 and 4 (values 5, 4, 2) are still waiting. On the second lap, the 5 at step 6 answers the 2 and the 4. Index 1, the maximum, is never answered and keeps -1.

Time: O(n). The loop runs 2n times, and each index is pushed once and popped at most once, so the pops add at most n more. Space: O(n) for the stack. Checked against the brute force on 500 random lists with many duplicates.

The whole thing is the core lesson's next_greater with two changes: range(2 * n) with % n, and the if step < n guard.

Edge cases

• All equal: nothing ever pops, every answer stays -1.
• One element: it cannot be bigger than itself: [-1].
• Several copies of the maximum: all get -1, because the comparison is strict.
• The maximum at the end, like [1, 2, 3]: 3 wraps around and meets only smaller values: [2, 3, -1].
• Empty list (outside the constraints): the loops do nothing and [] comes back.

Follow-ups

• "Next Greater Element I": a short list a whose values all appear in a longer list b; answer for each value of a using b. Run the non-circular stack over b, store the answers in a dictionary from value to next greater, then look each value of a up. O(len(a) + len(b)).
• "Previous greater element." Scan from right to left with the same code, or, scanning left to right, read the stack's top just before pushing — after the pops, it is the nearest bigger value on the left.
• "Next greater node in a linked list." Copy the values into a list first, or push (position, value) pairs while walking the list; the stack logic is unchanged.