Next Permutation

Problem

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

The next permutation is the lexicographically next greater permutation. If no such arrangement exists, rearrange nums into the lowest possible order (sorted ascending).

The replacement must be in place and use only constant extra memory.

Input / Output Format

Input: Array nums (modified in-place). Output: None — nums is mutated.

Examples

Example 1

Input: nums = [1,2,3] → Output: [1,3,2]

Example 2

Input: nums = [3,2,1] → Output: [1,2,3] (wraps)

Example 3

Input: nums = [1,1,5] → Output: [1,5,1]

Approach Hints

1. Scan from right; find first i where nums[i] < nums[i+1]. If none, reverse entire array (highest permutation → return lowest).
2. From right, find first j > i with nums[j] > nums[i].
3. Swap nums[i] and nums[j].
4. Reverse nums[i+1:] (the suffix is descending; reversing makes it ascending → smallest greater perm).

Time: O(n). Space: O(1).