Next Permutation
Medium
Given an array of integers nums, rearrange the numbers into the lexicographically next greater permutation of numbers.
If such an arrangement is not possible, rearrange the array into the lowest possible order (ascending order).
The rearrangement must be performed in-place and use only constant extra memory.
Example 1
Input
n = 3 nums = [1, 2, 3]
Output
[1, 3, 2]
Explanation
The next permutation after [1, 2, 3] is [1, 3, 2].
Example 2
Input
n = 3 nums = [3, 2, 1]
Output
[1, 2, 3]
Explanation
There is no greater permutation, so the array is rearranged into ascending order.
Constraints
1 <= n <= 10^5
-10^9 <= nums[i] <= 10^9
The rearrangement must be performed in-place.
Use constant extra memory.
Hints:
Hint 1
Starting from the right, find the first index where:
nums[i] < nums[i + 1]
Hint 2
Find the smallest element to the right of i that is greater than nums[i], then swap them.
Auto
Loading editor...
Input
Expected Output