## Description

https://leetcode.com/problems/next-permutation/

Implement **next permutation**, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

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

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

`1,2,3`

→ `1,3,2`

`3,2,1`

→ `1,2,3`

`1,1,5`

→ `1,5,1`

## Explanation

- find first decreasing element
- find number just larger than first decreasing element and swap with the first decreasing element
- sort all elements after the first decrease element position

## Python Solution

```
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# find first decreasing element
i = len(nums) - 2
while i > -1:
if nums[i] < nums[i + 1]:
break
i -= 1
# find number just larger than first decreasing element
j = i
min_large = sys.maxsize
for k in range(i, len(nums)):
if nums[k] > nums[i]:
min(min_large, nums[k])
j = k
# swap
temp = nums[j]
nums[j] = nums[i]
nums[i] = temp
# sort all elements after the first decrease element position
nums[i + 1:] = sorted(nums[i + 1:])
```

- Time Complexity: ~N
- Space Complexity: ~1

I found that solution very popular and helpful:

https://www.youtube.com/watch?v=tC-aM1rG1HA&ab_channel=EricProgramming

Leetcode link is wrong