# 31. Next Permutation

## LeetCode [**31. Next Permutation**](https://leetcode-cn.com/problems/next-permutation/)\*\*\*\*

### Description

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

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

The replacement must be [**in place**](http://en.wikipedia.org/wiki/In-place_algorithm) and use only constant extra memory.

**Example 1:**

```
Input: nums = [1,2,3]
Output: [1,3,2]
```

**Example 2:**

```
Input: nums = [3,2,1]
Output: [1,2,3]
```

**Example 3:**

```
Input: nums = [1,1,5]
Output: [1,5,1]
```

**Example 4:**

```
Input: nums = [1]
Output: [1]
```

**Constraints:**

* `1 <= nums.length <= 100`
* `0 <= nums[i] <= 100`

### Tags

Array

### Solution

The basic idea is to find a permutation which is just larger than the current one but with the smallest possible gap.

We need to find the first two successive number `nums[i]` and `nums[j]` from the right, which satisfy `nums[i] < nums[j]`. If no such pair, what should we do is just reverse the whole array, because it has already been the last permutation and we need to rearrange it as the lowest possible order.

Now, `nums[j:]` is in descending order. We firstly find a position k where `nums[k] > nums[i]` from the right. Secondly, swap the both. Lastly, reverse the `nums[j:]` (which is still in descending order) to make the permutation as small as possible.

### Complexity

* Time complexity: $$O(n)$$
* Space complexity: $$O(1)$$

### Code

```go
func nextPermutation(nums []int) {
	i, j, k := len(nums)-2, len(nums)-1, len(nums)-1
	for i >= 0 && nums[i] >= nums[j] { // find the first ascending pair in inverted order
		i--
		j--
	}
	if i >= 0 { // if nums is not sorted in descending order
		for nums[i] >= nums[k] { // find the first k that nums[k] > nums[i] in inverted order
			k--
		}
		nums[i], nums[k] = nums[k], nums[i] // swap them
	}
	for i, j := j, len(nums)-1; i < j; i, j = i+1, j-1 { // reverse the remain descending part
		nums[i], nums[j] = nums[j], nums[i]
	}
}
```

## Reference

1. [下一个排列算法详解：思路+推导+步骤，看不懂算我输！](https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/)