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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://joshualbarb.gitbook.io/leetcode-problems/arrangement/next-permutation.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.