> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/iv.-permutations-and-subsets/31.-next-permutation.md).

# 31. Next Permutation

* Find the element should be replaced, \[1, 2, 7, 6, 5, 4], 2 is the number.
* find the element just a little larger than 2, swap(2, 4) --- can save time
* reverse \[7, 6, 5, 2]
* result -> \[1, 2, 4, 2, 5, 6, 7]

{% tabs %}
{% tab title="Java(O(N\*log N)" %}

```java
class Solution {
    public void nextPermutation(int[] nums) {
        if(nums.length == 1) return;
        
        // [i, -1] should be rearranged
        int i = nums.length - 2;
        for(; i >= 0; i --) 
            if(nums[i] < nums[i+1]) 
                break;
        
        // find the index j which number is just bigger than nums[i]
        Arrays.sort(nums, i+1, nums.length);
        if(i == -1) return;  // [3, 2, 1]
        
        int j = insertPosition(nums, i+1, nums[i]);
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    private int insertPosition(int[] nums, int i, int goal) {
        int left = i, right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left)/2;
            if(goal >= nums[mid])
                left = mid +1;
            else
                right = mid;
        }
        return left;
    }
}
```

{% endtab %}

{% tab title="Java(O(N))" %}

```java
class Solution {
    public void nextPermutation(int[] nums) {
        if(nums.length == 1) return;
        
        // [i, -1] should be rearranged
        int i = nums.length - 2;
        while(i >= 0 && nums[i] >= nums[i+1])
            i --;
        if(i == -1) {
            reverse(nums, 0);
            return;
        }
        
        // find the index j which number is just bigger than nums[i]
        int j = nums.length - 1;
        while(nums[j] <= nums[i])
            j --;
        
        swap(nums, i, j);
        reverse(nums, i+1);
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    private void reverse(int[] nums, int start) {
        int i = start, j = nums.length-1;
        while(i < j) {
            swap(nums, i, j);
            i ++;
            j --;
        }
    }
}
```

{% endtab %}

{% tab title="Python" %}

```python
// Some code
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if nums == sorted(nums, reverse=True):
            nums.reverse()
            return nums
        
        # find the element need to be replaced
        for i in reversed(range(len(nums)-1)):
            if nums[i] < nums[i+1]:
                break
        
        # replace this element with the element a little big than it
        a = nums[i]
        replace = i + 1
        for j in range(i+2, len(nums)):
            if nums[j] > a and nums[j] < nums[replace]:
                replace = j
        temp = nums[replace]
        nums[replace] = nums[i]
        nums[i] = temp
        
        # sort the right side elements in acending order
        nums[i+1:] = sorted(nums[i+1:])
        
        return nums
```

{% endtab %}
{% endtabs %}