# 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

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | An integer array `answer` |
| `answer[i]` | The next greater element of `nums[i]` |
| Default value | `-1` if no greater element exists |

Function shape:

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

## Examples

Example 1:

```python
nums = [1, 2, 1]
```

For index `0`, the value is `1`.

The next value is `2`, and `2 > 1`.

So:

```python
answer[0] = 2
```

For index `1`, the value is `2`.

Looking forward circularly, we see:

```text
1, 1
```

Neither value is greater than `2`.

So:

```python
answer[1] = -1
```

For index `2`, the value is `1`.

After wrapping around, we see:

```text
1, 2
```

The first greater value is `2`.

So:

```python
answer[2] = 2
```

The final answer is:

```python
[2, -1, 2]
```

Example 2:

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

The answers are:

```python
[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:

```python
j = (i + step) % n
```

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

```python
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:

```text
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:

```python
index = i % n
```

## Algorithm

Let `n = len(nums)`.

Create:

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

The stack stores values, not indices.

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

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

Convert the virtual index into a real index:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each value is pushed and popped at most twice |
| Space | `O(n)` | The stack can contain up to `n` values |

The array is not physically doubled.

We only simulate circular access using modulo.

## Implementation

```python
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`:

```python
ans = [-1] * n
```

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

The stack stores possible next greater values:

```python
stack = []
```

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

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

The real index is computed using modulo:

```python
idx = i % n
```

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

Before using the stack, remove values that cannot help:

```python
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:

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

Then we push the current value for future positions:

```python
stack.append(nums[idx])
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `[1, 2, 1]` | Basic circular case |
| `[1, 2, 3, 4, 3]` | Last value wraps to find `4` |
| Strictly decreasing | Most values must wrap to the first element |
| All equal | Equal values are not greater |
| Single element | No other value exists |