# LeetCode 31: Next Permutation

## Problem Restatement

We are given an integer array `nums`.

We need to rearrange it into the next lexicographically greater permutation.

If no greater permutation exists, we rearrange it into the smallest possible permutation, which is ascending order.

The replacement must be done in place and must use only constant extra memory. The constraints are `1 <= nums.length <= 100` and `0 <= nums[i] <= 100`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | Nothing returned |
| Required mutation | Modify `nums` in place |
| If next permutation exists | Rearrange to the next greater permutation |
| If no next permutation exists | Rearrange to ascending order |
| Extra space | `O(1)` |

Function shape:

```python
def nextPermutation(nums: list[int]) -> None:
    ...
```

## Examples

Example 1:

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

All permutations in sorted order are:

```python
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
```

The next permutation after `[1, 2, 3]` is:

```python
[1, 3, 2]
```

Example 2:

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

This is already the largest permutation.

So we wrap around to the smallest permutation:

```python
[1, 2, 3]
```

Example 3:

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

The next permutation is:

```python
[1, 5, 1]
```

## First Thought: Generate All Permutations

A direct approach is:

1. Generate every permutation of `nums`.
2. Sort all permutations lexicographically.
3. Find the current permutation.
4. Return the next one.

This works conceptually, but it is far too expensive.

For an array of length `n`, there can be `n!` permutations.

Even for `n = 10`, this is already millions of permutations.

We need to compute the next permutation directly.

## Key Insight

To get the next permutation, we want the smallest possible increase.

That means we should change the array as far to the right as possible.

Consider:

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

Look at the suffix:

```python
[5, 4, 2]
```

This suffix is descending.

A descending suffix is already the largest possible arrangement of those elements.

So we cannot make the array larger by only rearranging `[5, 4, 2]`.

We need to change the element just before that suffix:

```python
[1, 3, 5, 4, 2]
    ^
```

The pivot is `3`.

To make the next permutation, we replace `3` with the smallest number in the suffix that is larger than `3`.

The suffix has:

```python
[5, 4, 2]
```

The numbers larger than `3` are `5` and `4`.

The smallest larger value is `4`.

Swap `3` and `4`:

```python
[1, 4, 5, 3, 2]
```

Now the prefix `[1, 4]` is fixed. To make the whole array as small as possible after this increase, sort the suffix ascending:

```python
[1, 4, 2, 3, 5]
```

Because the suffix was descending before the swap, we can reverse it instead of sorting it.

## Algorithm

Scan from right to left and find the first index `i` such that:

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

This index is the pivot.

If no such index exists, the whole array is descending. That means it is already the largest permutation. Reverse the whole array and stop.

Otherwise, scan from right to left again and find the first index `j` such that:

```python
nums[j] > nums[i]
```

Swap `nums[i]` and `nums[j]`.

Then reverse the suffix starting at `i + 1`.

## Correctness

The scan from right to left finds the first place where the descending suffix begins. Everything after index `i` is in non-increasing order, so that suffix is the largest possible arrangement of those suffix elements.

To get a greater permutation, we must increase some position. Choosing the rightmost possible pivot `i` gives the smallest change to the prefix.

After choosing `i`, we need to replace `nums[i]` with the smallest value in the suffix that is larger than it. Since the suffix is non-increasing, scanning from the right finds exactly that value.

After the swap, the prefix becomes slightly larger than before. To make the full permutation as small as possible with that new prefix, the suffix must be arranged in ascending order.

The suffix after the swap is still in non-increasing order, so reversing it gives ascending order.

Therefore, the algorithm produces the smallest permutation that is greater than the original. If no pivot exists, the original array is the largest permutation, so reversing it gives the smallest permutation.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan and reverse the array at most once |
| Space | `O(1)` | We modify the array in place |

## Implementation

```python
class Solution:
    def nextPermutation(self, nums: list[int]) -> None:
        n = len(nums)

        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        if i >= 0:
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1

            nums[i], nums[j] = nums[j], nums[i]

        left = i + 1
        right = n - 1

        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1
```

## Code Explanation

Start from the second-to-last index:

```python
i = n - 2
```

We move left while the array is descending from that point:

```python
while i >= 0 and nums[i] >= nums[i + 1]:
    i -= 1
```

When the loop stops, either `i == -1`, or `nums[i] < nums[i + 1]`.

If `i >= 0`, we found a pivot.

```python
if i >= 0:
```

Then we find the rightmost element larger than the pivot:

```python
j = n - 1
while nums[j] <= nums[i]:
    j -= 1
```

Swap the pivot with that element:

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

Finally, reverse the suffix after the pivot:

```python
left = i + 1
right = n - 1

while left < right:
    nums[left], nums[right] = nums[right], nums[left]
    left += 1
    right -= 1
```

If `i == -1`, this reverses the whole array, which handles the descending case.

## Testing

```python
def check(nums: list[int], expected: list[int]) -> None:
    original = nums[:]
    Solution().nextPermutation(nums)
    assert nums == expected, (original, nums, expected)

def run_tests():
    check([1, 2, 3], [1, 3, 2])
    check([3, 2, 1], [1, 2, 3])
    check([1, 1, 5], [1, 5, 1])
    check([1], [1])
    check([1, 3, 5, 4, 2], [1, 4, 2, 3, 5])
    check([2, 3, 1], [3, 1, 2])
    check([1, 5, 1], [5, 1, 1])
    check([2, 2, 7, 5, 4, 3, 2, 2, 1], [2, 3, 1, 2, 2, 2, 4, 5, 7])

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1,2,3]` | Simple increasing case |
| `[3,2,1]` | Already largest permutation |
| `[1,1,5]` | Duplicate values |
| `[1]` | Minimum input |
| `[1,3,5,4,2]` | Pivot with descending suffix |
| `[2,3,1]` | Pivot near the beginning |
| `[1,5,1]` | Duplicate with pivot swap |
| Larger mixed case | Checks pivot, swap, and suffix reversal together |