83. Next Permutation

Rearrange nums into the lexicographically next greater permutation. If already the greatest (descending), rearrange to the smallest (ascending). In-place, O(1) extra memory.

Input: Integer array nums.

Output: Array rearranged to next permutation.

Examples

Input: [1,2,3]
Output: [1,3,2]
Explanation: Next permutation after [1,2,3].

Input: [3,2,1]
Output: [1,2,3]
Explanation: No next — wrap to smallest.

Input: [1,1,5]
Output: [1,5,1]
Explanation: Next after [1,1,5].

Constraints

• 1<=nums.length<=100
• 0<=nums[i]<=100

Asked by