# LeetCode 31. Next Permutation

## 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

1. find first decreasing element
2. find number just larger than first decreasing element and swap with the first decreasing element
3. 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

## 3 Thoughts to “LeetCode 31. Next Permutation”

1. DeveloperLite says:

Heyy, I made a small video for this problem using Two Pointers, you can check this out !!
Please subscribe if you find this useful:) !!
2. Chiu says: