# LeetCode 556: Next Greater Element III

## Problem Restatement

We are given a positive integer `n`.

We need to rearrange its digits to form the smallest integer that is greater than `n`.

The new integer must use exactly the same digits as `n`.

If no greater integer can be formed, return `-1`.

If the answer is greater than the 32-bit signed integer limit, return `-1`.

The official constraint is:

```python
1 <= n <= 2**31 - 1
```

The return value must also fit inside:

```python
2**31 - 1
```

The problem examples include `n = 12`, output `21`, and `n = 21`, output `-1`. The statement requires the smallest greater integer using exactly the same digits.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A positive integer `n` |
| Output | The next greater integer using the same digits |
| Return `-1` when | No greater arrangement exists |
| Return `-1` when | The answer exceeds `2^31 - 1` |

Example function shape:

```python
def nextGreaterElement(n: int) -> int:
    ...
```

## Examples

Example 1:

```python
n = 12
```

The digits are:

```python
["1", "2"]
```

The only greater arrangement is:

```python
21
```

So the answer is:

```python
21
```

Example 2:

```python
n = 21
```

The digits are already in descending order:

```python
2, 1
```

There is no way to rearrange them into a greater number.

So the answer is:

```python
-1
```

Example 3:

```python
n = 12443322
```

We want the next greater number, not just any greater number.

The answer is:

```python
13222344
```

## First Thought: Try All Permutations

One direct idea is to generate every permutation of the digits.

Then we can keep only the numbers greater than `n`, sort them, and return the smallest one.

This is correct for small inputs, but it is too expensive.

If `n` has `d` digits, there can be up to:

```python
d!
```

permutations.

A 32-bit integer has at most 10 digits, so this may look possible, but handling duplicates, sorting, and converting many permutations is unnecessary. There is a direct linear algorithm.

## Key Insight

This is the same idea as the classic next permutation algorithm.

We want the next number in lexicographic order of digit sequences.

To make the number just slightly larger, we should change the number as far to the right as possible.

Consider:

```python
n = 12443322
```

Digits:

```python
1 2 4 4 3 3 2 2
```

Scan from right to left and find the first position where a digit is smaller than the digit after it.

That position is the pivot.

Here:

```python
2 < 4
```

at the second digit.

The suffix after that pivot is:

```python
4 4 3 3 2 2
```

This suffix is in descending order, which means it is already the largest possible arrangement for those digits. To get the next greater number, we must increase the pivot slightly, then make the suffix as small as possible.

## Algorithm

Convert `n` to a list of digit characters.

1. Find the pivot:
   1. Start from the second-to-last digit.
   2. Move left while `digits[i] >= digits[i + 1]`.
   3. If no pivot exists, return `-1`.

2. Find the swap digit:
   1. Start from the last digit.
   2. Move left until finding a digit greater than `digits[i]`.

3. Swap the pivot and the swap digit.

4. Reverse the suffix after the pivot.

5. Convert the digits back to an integer.

6. If the result is greater than `2^31 - 1`, return `-1`. Otherwise, return the result.

## Why Reversing the Suffix Works

Before the swap, the suffix after the pivot is in descending order.

After we swap the pivot with the smallest possible larger digit from the suffix, the suffix is still in descending order.

To get the smallest number greater than the original, the suffix must become as small as possible.

For digits, the smallest order is ascending order.

Since the suffix is descending, reversing it makes it ascending.

## Correctness

The algorithm finds the rightmost pivot `i` such that:

```python
digits[i] < digits[i + 1]
```

Every digit after `i` forms a non-increasing suffix. This means the suffix is already the largest possible arrangement of those suffix digits. Therefore, no rearrangement only inside the suffix can make the number greater.

So any greater number using the same digits must change position `i` or some earlier position. To make the increase as small as possible, we change the rightmost possible position, which is exactly `i`.

Next, the algorithm chooses the rightmost digit greater than `digits[i]`. Because the suffix is non-increasing, this is the smallest digit in the suffix that is still greater than the pivot. Swapping with it gives the smallest possible increase at position `i`.

Finally, the algorithm reverses the suffix to make it ascending. This produces the smallest possible suffix after increasing the pivot.

Therefore, the result is greater than `n`, uses exactly the same digits, and is the smallest such integer. If no pivot exists, all digits are in descending order, so no greater arrangement exists.

## Complexity

Let `d` be the number of digits in `n`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(d)` | We scan and reverse the digit list |
| Space | `O(d)` | We store the digits as a list |

Since `n` is a 32-bit integer, `d <= 10`, but the algorithm is still linear in the number of digits.

## Implementation

```python
class Solution:
    def nextGreaterElement(self, n: int) -> int:
        digits = list(str(n))
        length = len(digits)

        i = length - 2
        while i >= 0 and digits[i] >= digits[i + 1]:
            i -= 1

        if i < 0:
            return -1

        j = length - 1
        while digits[j] <= digits[i]:
            j -= 1

        digits[i], digits[j] = digits[j], digits[i]

        digits[i + 1:] = reversed(digits[i + 1:])

        ans = int("".join(digits))
        if ans > 2**31 - 1:
            return -1

        return ans
```

## Code Explanation

We first convert the integer into a mutable list:

```python
digits = list(str(n))
```

Then we find the pivot:

```python
i = length - 2
while i >= 0 and digits[i] >= digits[i + 1]:
    i -= 1
```

If no pivot exists, the digits are in descending order:

```python
if i < 0:
    return -1
```

Then we find the digit to swap with the pivot:

```python
j = length - 1
while digits[j] <= digits[i]:
    j -= 1
```

Because the suffix is descending, scanning from the right finds the smallest digit greater than the pivot.

Then we swap:

```python
digits[i], digits[j] = digits[j], digits[i]
```

Finally, we reverse the suffix:

```python
digits[i + 1:] = reversed(digits[i + 1:])
```

This makes the suffix as small as possible.

After rebuilding the integer, we check the 32-bit limit:

```python
ans = int("".join(digits))
if ans > 2**31 - 1:
    return -1
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.nextGreaterElement(12) == 21
    assert s.nextGreaterElement(21) == -1
    assert s.nextGreaterElement(123) == 132
    assert s.nextGreaterElement(12443322) == 13222344
    assert s.nextGreaterElement(1999999999) == -1
    assert s.nextGreaterElement(230241) == 230412
    assert s.nextGreaterElement(115) == 151
    assert s.nextGreaterElement(9) == -1

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `12` | Smallest sample with a valid answer |
| `21` | Digits already descending |
| `123` | Simple next permutation |
| `12443322` | Larger case with repeated digits |
| `1999999999` | Next arrangement exceeds 32-bit limit |
| `230241` | Pivot occurs near the middle |
| `115` | Repeated digit handling |
| `9` | Single digit cannot form a greater number |