Next Permutation

First Missing Positive

Isomorphic Strings

Return the lexicographically next greater permutation, or the lowest ordering if none exists.

Given an integer array `nums`, return the lexicographically next greater permutation of its values.

If `nums` is already the highest possible permutation, return the lowest possible ordering instead (ascending order).

Unlike the classic LeetCode version that mutates the array in place and returns `void`, this judge is functional-style: return the resulting `int[]` directly.

**Input / output**
- Input: `nums: int[]`
- Output: `int[]`

**Examples**
1. `nums = [1,2,3]` returns `[1,3,2]`.
2. `nums = [3,2,1]` returns `[1,2,3]`.
3. `nums = [1,1,5]` returns `[1,5,1]`.

**Constraints**
- `1 <= nums.length <= 100`
- `-100 <= nums[i] <= 100`

**Follow-up**
Can you explain why the suffix to the right of the pivot is guaranteed to be non-increasing, and therefore can be reversed instead of fully sorted?

- A permutation is "next" only if it is larger than the current one but as small as possible among all larger permutations.
- That means we must change the array as far to the right as possible, then keep the suffix minimal.

Understand the lexicographic rule

- Scan pivot positions from right to left.
- For the first pivot that has a larger value somewhere to its right, swap in the smallest larger value and then sort the suffix.
- This is correct, but the explicit suffix sort costs extra work.

Brute-force by rebuilding the suffix

- The first index from the right where `nums[i] < nums[i + 1]` is the pivot.
- Everything to its right is already in descending order, so once we swap in the next-larger value, reversing that suffix makes it as small as possible.

Exploit the descending suffix

- Find the pivot from the right.
- Find the first value from the right that is larger than the pivot and swap them.
- Reverse the suffix in place instead of sorting it.

Build the optimal O(n) transformation

Trace `nums = [1,2,3,6,5,4]`.

| step | state | explanation |
|---|---|---|
| find pivot | `[1,2,3,6,5,4]` | scan from the right; `3 < 6`, so pivot index is `2` |
| find swap | `[1,2,3,6,5,4]` | the first value from the right larger than `3` is `4` |
| swap | `[1,2,4,6,5,3]` | now the prefix is the next-larger prefix |
| reverse suffix | `[1,2,4,3,5,6]` | the suffix was descending, so reversing it makes it minimal |

Dry run / state trace

- Sorting the whole array after the swap, which is correct but slower than necessary.
- Picking a larger suffix value that is not the smallest possible larger value.
- Forgetting the "already highest permutation" case, which should wrap to ascending order.
- Follow-up: how would you do the in-place mutation-only LeetCode version if the function returned `void`?

Common mistakes and follow-ups

- Single-element arrays stay unchanged.
- Arrays with all equal values also stay unchanged.
- A fully descending array should wrap to ascending order.
- Duplicates in the suffix still work because we swap with the rightmost value that is just large enough.

Edge cases to test mentally

Find the pivot, swap with the next-larger value from the right, then reverse the descending suffix. This runs in `O(n)` time and uses `O(n)` output space here only because we return a new array rather than mutating the caller-owned one.