Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The input is an integer array nums, but the array is circular. After the last index, the scan wraps back to index 0.

For each index i, the task is to find the first value that is strictly greater than nums[i] when walking forward through this circular array. If no greater value appears before returning to i, the answer for that index is -1.

For example, in [1, 2, 1]:

  • The next greater value after the first 1 is 2.
  • The value 2 has no greater value anywhere in the circular scan, so its answer is -1.
  • The last 1 wraps around and finds 2, so its answer is also 2.

The important phrase is “first greater value to the right, with wraparound.” That points to a stack problem, not a nested-loop problem.

The optimal idea

A brute-force solution checks up to n - 1 later positions for every index, which costs O(n^2). The better solution keeps a stack of indices whose next greater value has not been found yet.

Scan the array twice. The first pass pushes each index onto the stack. The second pass does not push new indices; it only gives earlier indices a chance to see values that appear after wraparound.

While scanning a value current_value, any pending index at the top of the stack with a smaller value has just found its answer:

answer[pending_index] = current_value

Then pop that pending index, because its first greater value has been resolved. Keep popping while the current value is greater than the value at the stack top.

This works because the stack stores unresolved indices in decreasing-value order. Smaller values wait until a larger value arrives; larger or equal values stay because the current value is not enough to solve them.

How to derive it in an interview

Start with one index. If the scan moves right and sees only smaller or equal values, that index remains unresolved. Once a larger value appears, that larger value is the answer for the index and for any smaller unresolved values immediately before it.

That suggests grouping unresolved indices instead of rescanning them one by one. A stack is the natural fit because the most recently seen unresolved value is the first one that the current value might resolve.

For a normal, non-circular array, one left-to-right pass is enough. For a circular array, the only extra trick is to simulate a second pass by using:

actual_index = virtual_index % n

The algorithm still stores each real index only once. It just looks at the values twice so elements near the end can find answers near the beginning.

Python solution

from typing import Sequence


def next_greater_elements_circular(nums: Sequence[int]) -> list[int]:
    """
    Return the next strictly greater value for each position in a circular array.

    Each original index is pushed onto the stack once. The second traversal only
    supplies wraparound values that may resolve still-pending indices.
    """
    length = len(nums)
    next_greater_values = [-1] * length
    pending_indices: list[int] = []

    for virtual_index in range(2 * length):
        actual_index = virtual_index % length
        current_value = nums[actual_index]

        # Every smaller pending value has found its first greater value.
        while pending_indices and nums[pending_indices[-1]] < current_value:
            resolved_index = pending_indices.pop()
            next_greater_values[resolved_index] = current_value

        # Push each real index only during the first pass. During the second
        # pass, values are used only to resolve earlier pending indices.
        if virtual_index < length:
            pending_indices.append(actual_index)

    return next_greater_values


class Solution:
    def nextGreaterElements(self, nums: list[int]) -> list[int]:
        """LeetCode entry point."""
        return next_greater_elements_circular(nums)

Why this works

The stack contains indices whose next greater value has not appeared yet. From bottom to top, their values are in non-increasing order. If a new value is not greater than the stack top, it cannot resolve that top index, and it also cannot resolve any larger value below it.

If a new value is greater than the stack top, it is the first greater value for that top index. Nothing earlier in the scan resolved that index, and the current value is the first later value large enough to do so. After popping that index, the same current value may also resolve more smaller pending values.

Scanning 2 * n virtual positions gives every index a full circular lookahead. An index near the end sees values from the beginning during the second pass. The algorithm does not push indices during that second pass, so it cannot loop forever or create duplicate work.

Every index is pushed once and popped at most once. The scan has 2n iterations, so the time complexity is O(n). The result array and stack use O(n) space.

Interview follow-ups

How would the solution change if the array were not circular?

For a normal array, scan only once from left to right. The same pending-index stack works: when the current value is greater than the value at the stack top, it resolves that pending index.

The circular problem needs a second virtual pass only because an element near the end may find its next greater value near the beginning. Without wraparound, those beginning values are not to the right, so the second pass should be removed. The complexity remains O(n) time and O(n) space.

How would you return the next greater index instead of the value?

Keep the same stack of unresolved indices, but assign actual_index instead of current_value when resolving an entry. The result array would start as [-1] * n, and the update would become:

next_greater_indices[resolved_index] = actual_index

This works because the stack logic identifies exactly when the current position is the first greater position after a pending index. The only tradeoff is that callers now need to look up nums[result[i]] themselves if they want the value.

What if the interviewer asks for the distance to the next greater value?

Again, the stack logic stays the same. When actual_index resolves resolved_index, compute the circular distance:

(actual_index - resolved_index) % n

That distance is positive because the resolved index is matched only after the scan has moved forward in virtual time. This variant is useful when the question asks how many steps to move rather than which value is found. The time and space complexity stay O(n).

What if the condition changed from strictly greater to greater than or equal?

The comparison in the while loop must change from < current_value to <= current_value, but the circular edge case needs care. An element should not satisfy itself after a full wraparound.

One clean approach is to scan from right to left for 2n - 1 virtual positions, maintain candidate indices, and ignore candidates whose virtual distance is 0 or too large. Another practical approach is to keep the left-to-right stack but stop the second pass before each index could match itself. The key idea is that equal values now become valid answers, so duplicates can no longer simply stay on the stack the way they do in the strictly-greater version.

What if values are updated between queries?

If updates are rare, recomputing the entire answer after each update is often the right engineering choice. The monotonic-stack pass is linear, simple, and hard to get wrong.

If updates are frequent and the array is large, this becomes a dynamic range-query problem rather than a standard interview stack problem. A segment tree can find the first position with value greater than a target over a range, and the circular lookup can be split into the range to the right of i plus the range before i. That supports updates and queries in logarithmic time, but the implementation is much more complex than the static O(n) stack solution.

Practical takeaway

Next Greater Element II is the circular version of a classic monotonic-stack pattern. The stack stores indices that are still waiting for a larger value. Scanning twice gives every index its wraparound lookahead, and pushing each index only once keeps the whole solution linear.