> For the complete documentation index, see [llms.txt](https://joshualbarb.gitbook.io/leetcode-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://joshualbarb.gitbook.io/leetcode-problems/arrangement/next-permutation.md).

# Next Permutation

## Problem

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.

{% hint style="info" %}
For example:

```
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]
```

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

{% endhint %}

### Thought Process

* Notice how that a section that is strictly **decreasing** has exhausted itself and reached its last placement, i.e. the highest permutation available for that section

* Since a strictly decreasing section means that that section is on it's last/highest permutation, this means the overall next permuation in the array has to begin in a placement where an element is at the beginning of an ascending order section, i.e. the element before the strictly decreasing section.

{% hint style="info" %}
Example: 1 **2** 3 ---> 1 3 2 

Example: 1 2 **3** 6 5 4 ---> 1 2 4 3 5 6 4  

(Bolded number is the slot that still has options to explore)
{% endhint %}

* Why we choose an element before a strictly decreasing section is because this slot/index still has options to explore and has not exhausted all of its permuations because it is not the highest permutation for this section which includes the slot. 

* The slot we identify as the next permutation has to be swapped with the rightmost **first** **larger** **number**, since this will produce the next greater permutation
  * w

* If we identify the whole array being in descending order, then we just have to flip the array horizontally to recieve the lowest possible order

## Solution

```
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
   
        i = len(nums) - 2 
        
        #finding number that's in ascending order
        while(i >= 0 and nums[i] >= nums[i+1]):
            i-=1
            
        #if the array is in the highest perm.
        if(i==-1):
            for n in range(len(nums)//2):
                temp = nums[n]
                nums[n] = nums[len(nums)-1-n]
                nums[len(nums)-1-n] = temp
            return
         
        #finding the rightmost first larger number
        k = len(nums)-1
        while(nums[k] <= nums[i]):
            k-=1
            
        nums[i], nums[k] = nums[k], nums[i]
        
        l = i+1
        r = len(nums)-1
        
        #rearranging the numbers in our new permutation
        while l <= r:
            nums[l], nums[r] = nums[r], nums[l]
            l+=1
            r-=1
        
        return nums  
        
```

## Key Facts

* We are looking for a section that is strictly decreasing, as this section is on it's last permuation that is the greatest&#x20;

* A section that is strictly decreasing means it is on it's highest permuation. The slot right **before** this means this is the beginning positon of the next permuation&#x20;

* We need to switch the element right before the decreasing section (i.e. an element that's the start of ascending) with the rightmost **first larger** number

## Time Complexity

* **Time:** $$O(n)$$&#x20;
* **Space:** $$O(1)$$&#x20;