Next Permutation of an Array

Problem

A permutation is an arrangement of elements of an array.
The next permutation is the next lexicographically greater arrangement of numbers.

If no greater permutation exists, rearrange the array in ascending order.

Examples

Input

nums = [1,2,3]

Output

[1,3,2]

Input

nums = [3,2,1]

Output

[1,2,3]

Input

nums = [1,1,5]

Output

[1,5,1]

Approach
Traverse from right and find the first element where nums[i] < nums[i+1].
Find the next larger element on the right side.
Swap these two elements.
Reverse the elements after position i.
This gives the next lexicographically greater permutation.

Python Code

class Solution:
def nextPermutation(self, nums: list[int]) -> None:
n = len(nums)
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
j = n - 1
while nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
left, right = i + 1, n - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1

Output
[1,3,2]