31. Next Permutation
You are given an array of integers nums — one particular arrangement (permutation) of its values. Rearrange it into the arrangement that comes immediately after it in dictionary (lexicographic) order, and return the resulting array.
If nums is already the greatest possible arrangement of its values, wrap around: return the smallest arrangement instead — the values sorted in ascending order.
The successor of any arrangement is unique, so there is exactly one correct answer for every input. Try to do the rearrangement using only constant extra memory.
Example 1:
Input: nums = [1, 2, 3]
Output: [1, 3, 2]
Explanation: Of the six orderings of these values, [1, 3, 2] is the one that comes right after [1, 2, 3].
Example 2:
Input: nums = [3, 2, 1]
Output: [1, 2, 3]
Explanation: [3, 2, 1] is the last ordering, so the answer wraps around to the fully ascending one.
Example 3:
Input: nums = [1, 1, 5]
Output: [1, 5, 1]
Explanation: Duplicates are fine: the arrangement right after [1, 1, 5] is [1, 5, 1].
Constraints:
- 1 ≤ nums.length ≤ 100
- 0 ≤ nums[i] ≤ 100
Hints:
Scan from the right. A suffix that is non-increasing (like 7 5 3) is already the largest arrangement of those values — nothing you shuffle inside it can make the array bigger.
The first index i (from the right) with nums[i] < nums[i+1] is the pivot. Swap it with the smallest suffix value that beats it — the rightmost suffix element greater than nums[i].
After the swap the suffix is still non-increasing, so reversing it makes the tail as small as possible. No sort needed.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 2, 3]
Expected output: [1, 3, 2]