LeetCode 503: Next Greater Element II

Problem Restatement

We are given a circular integer array nums.

For each element, we need to find the next greater element after it.

The word circular means that after the last element, we continue again from the first element.

If no greater element exists, the answer for that position is -1.

The official problem asks us to return the next greater number for every element in a circular integer array. The next element after nums[nums.length - 1] is nums[0].

Input and Output

Function shape:

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        ...

Examples

Example 1:

nums = [1, 2, 1]

For index 0, the value is 1.

The next value is 2, and 2 > 1.

So:

answer[0] = 2

For index 1, the value is 2.

Looking forward circularly, we see:

1, 1

Neither value is greater than 2.

So:

answer[1] = -1

For index 2, the value is 1.

After wrapping around, we see:

1, 2

The first greater value is 2.

So:

answer[2] = 2

The final answer is:

[2, -1, 2]

Example 2:

nums = [1, 2, 3, 4, 3]

The answers are:

[2, 3, 4, -1, 4]

The last value 3 wraps around and finds 4.

First Thought: Scan Forward for Each Index

A direct solution is to simulate the circular array for every index.

For each position i, look at the next n - 1 elements.

Use modulo to wrap around:

j = (i + step) % n

If we find a value greater than nums[i], store it and stop.

from typing import List

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [-1] * n

        for i in range(n):
            for step in range(1, n):
                j = (i + step) % n

                if nums[j] > nums[i]:
                    ans[i] = nums[j]
                    break

        return ans

Problem With Brute Force

The brute force solution may check almost every other element for every index.

If n is the length of nums, this costs:

O(n^2)

We need to avoid repeatedly scanning the same values.

The useful observation is that many smaller values can never be the next greater element once a larger value blocks them.

Key Insight

Use a monotonic stack.

The stack stores candidate values that may become the next greater element for positions to the left.

We process from right to left.

For each current value x, any stack value <= x is useless for x.

It cannot be the next greater element because it is not greater.

So we pop all values less than or equal to x.

After popping, if the stack is not empty, the top is the next greater element.

Because the array is circular, we scan the array twice.

Modulo indexing lets us simulate wrapping:

index = i % n

Algorithm

Let n = len(nums).

Create:

ans = [-1] * n
stack = []

The stack stores values, not indices.

Then iterate from right to left over 2 * n positions:

for i in range(2 * n - 1, -1, -1):

Convert the virtual index into a real index:

idx = i % n

For each nums[idx]:

1. Pop while the stack top is less than or equal to nums[idx].
2. If the stack is not empty, its top is the next greater element.
3. Store that value in ans[idx].
4. Push nums[idx] onto the stack.

The second pass gives each element access to values that appear before it in the original array.

Correctness

The traversal processes elements from right to left over a doubled view of the array.

For any position i, this doubled traversal exposes exactly the elements that appear after i in circular order.

The stack keeps only useful candidates.

When processing a value x, every value <= x is removed. Such a value cannot be the next greater element for x, since it is not greater than x.

After all smaller or equal values are removed, the top of the stack, if present, is the closest remaining greater value in the circular order represented by the traversal.

Thus ans[i] is set to the first greater value after nums[i].

If the stack is empty, no greater value exists, and the answer remains -1.

Since every index is processed under this rule, the returned array is correct.

Complexity

The array is not physically doubled.

We only simulate circular access using modulo.

Implementation

from typing import List

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [-1] * n
        stack = []

        for i in range(2 * n - 1, -1, -1):
            idx = i % n

            while stack and stack[-1] <= nums[idx]:
                stack.pop()

            if stack:
                ans[idx] = stack[-1]

            stack.append(nums[idx])

        return ans

Code Explanation

We initialize every answer as -1:

ans = [-1] * n

This is correct for any element that has no greater value.

The stack stores possible next greater values:

stack = []

We iterate through a virtual array of length 2 * n:

for i in range(2 * n - 1, -1, -1):

The real index is computed using modulo:

idx = i % n

This is how we handle circular behavior without creating a new array.

Before using the stack, remove values that cannot help:

while stack and stack[-1] <= nums[idx]:
    stack.pop()

After this loop, any value remaining at the top is greater than nums[idx].

So it is the answer:

if stack:
    ans[idx] = stack[-1]

Then we push the current value for future positions:

stack.append(nums[idx])

Testing

def test_next_greater_elements():
    s = Solution()

    assert s.nextGreaterElements([1, 2, 1]) == [2, -1, 2]
    assert s.nextGreaterElements([1, 2, 3, 4, 3]) == [2, 3, 4, -1, 4]
    assert s.nextGreaterElements([5, 4, 3, 2, 1]) == [-1, 5, 5, 5, 5]
    assert s.nextGreaterElements([1, 1, 1]) == [-1, -1, -1]
    assert s.nextGreaterElements([2]) == [-1]

    print("all tests passed")

Test meaning: