# Next Permutation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/next-permutation)
Canonical: https://scaleengineer.com/dsa/problems/next-permutation
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [ByteDance](https://scaleengineer.com/companies/bytedance), [DoorDash](https://scaleengineer.com/companies/doordash), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [Intuit](https://scaleengineer.com/companies/intuit), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Paytm](https://scaleengineer.com/companies/paytm), [ServiceNow](https://scaleengineer.com/companies/servicenow), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [VMware](https://scaleengineer.com/companies/vmware), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs), [Nike](https://scaleengineer.com/companies/nike), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Zepto](https://scaleengineer.com/companies/zepto), [Mitsogo](https://scaleengineer.com/companies/mitsogo), [HashedIn](https://scaleengineer.com/companies/hashedin), [Rubrik](https://scaleengineer.com/companies/rubrik), [Arcesium](https://scaleengineer.com/companies/arcesium), [Upstart](https://scaleengineer.com/companies/upstart)
---
## Problem
A **permutation** of an array of integers is an arrangement of its members into a sequence or linear order.

* For example, for `arr = [1,2,3]`, the following are all the permutations of `arr`: `[1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1]`.

The **next permutation** of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the **next permutation** of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

* For example, the next permutation of `arr = [1,2,3]` is `[1,3,2]`.
* Similarly, the next permutation of `arr = [2,3,1]` is `[3,1,2]`.
* While the next permutation of `arr = [3,2,1]` is `[1,2,3]` because `[3,2,1]` does not have a lexicographical larger rearrangement.

Given an array of integers `nums`, _find the next permutation of_ `nums`.

The replacement must be **[in place](http://en.wikipedia.org/wiki/In-place%5Falgorithm)** 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]

**Constraints:**

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

# Approaches
## Brute Force: Generate All Permutations
The most intuitive but highly inefficient approach is to generate all possible unique permutations of the input array. Once all permutations are generated, they can be sorted lexicographically. The permutation immediately following the input array in this sorted list is the desired next permutation. If the input array is the last one in the sorted list, the next permutation is the very first one (the smallest).
**Time:** O(N! * N * log(N!)) · **Space:** O(N * N!)
**Pros:** Conceptually straightforward and easy to understand.
**Cons:** Extremely high time complexity of at least O(N! * N), making it infeasible for N > 10.; Requires a large amount of extra space, O(N * N!), to store all permutations.; Will result in a 'Time Limit Exceeded' or 'Memory Limit Exceeded' error for the given constraints.
### Explanation
This method breaks the problem down into three main parts: generation, sorting, and searching.

First, we need a mechanism to generate every distinct arrangement of the numbers in the `nums` array. A standard backtracking algorithm is well-suited for this. We would recursively build permutations, ensuring we don't reuse elements and handle duplicates correctly to generate only unique permutations.

Second, after collecting all unique permutations into a list, we sort this list. The sorting criterion is lexicographical order, which means we compare permutations element by element from left to right.

Finally, we search for the original `nums` array within this sorted list. The element at the next index is our answer. If `nums` is the last element, we wrap around and take the first element of the list. The final step is to copy the found permutation back into the original `nums` array to satisfy the in-place modification requirement.

While this approach is conceptually simple, its factorial time and space complexity make it impractical for arrays of even moderate size, and it will not pass the given constraints.
### Algorithm
- 1. Generate all unique permutations of the `nums` array using a recursive backtracking approach.
- 2. Store these permutations in a list.
- 3. Sort the list of permutations lexicographically.
- 4. Find the index of the original `nums` permutation in the sorted list.
- 5. If the original permutation is the last one, the next permutation is the first one in the list. Otherwise, it's the one at the next index.
- 6. Modify the input `nums` array in-place by copying the elements from the found next permutation.

## Single-Pass In-Place Algorithm
A far more efficient solution can be achieved in a single pass over the array. The logic hinges on finding the rightmost element that can be increased to form the next lexicographically greater permutation. By making the smallest possible change at the rightmost position, we ensure the result is the immediate next permutation.
**Time:** O(N) · **Space:** O(1)
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1) as it modifies the array in-place.; Handles all edge cases, including duplicates and arrays that are already the largest permutation.
**Cons:** The logic can be non-intuitive to derive from scratch under pressure.
### Explanation
The algorithm is based on a key observation. To find the next permutation, we need to find the longest suffix of the array that is in decreasing order. The element just before this suffix is our 'pivot'. This pivot is the first element from the right that is smaller than its right neighbor. We need to swap this pivot with the smallest element in the suffix that is still larger than the pivot. After the swap, the suffix (which is still mostly in decreasing order) must be rearranged to its smallest possible form, which is ascending order. This is easily achieved by reversing the suffix.

Let's trace with `nums = [2,3,1]`:
1.  Scan from right to left. `nums[1]=3` is not less than `nums[2]=1`. `nums[0]=2` is less than `nums[1]=3`. So, our pivot index is `i = 0`.
2.  Scan the suffix `[3,1]` from right to left to find the smallest number greater than the pivot `nums[0]=2`. That number is `3` at index `j=1`.
3.  Swap `nums[i]` and `nums[j]`. The array becomes `[3,2,1]`.
4.  Reverse the subarray to the right of the pivot index `i`. The subarray from index `i+1=1` is `[2,1]`. Reversing it gives `[1,2]`.
5.  The final result is `[3,1,2]`.

If the entire array is in decreasing order (e.g., `[3,2,1]`), no pivot is found. This signifies it's the largest permutation. The next one is the smallest, achieved by reversing the whole array to get `[1,2,3]`.

```java
class Solution {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) return;

        // Step 1: Find the first element from the right that is smaller than its right neighbor.
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        // If such an element is found (i.e., the array is not in descending order)
        if (i >= 0) {
            // Step 2: Find the smallest element from the right that is greater than nums[i].
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            // Step 3: Swap nums[i] and nums[j].
            swap(nums, i, j);
        }

        // Step 4: Reverse the subarray from i + 1 to the end.
        // If i was -1 (array was in descending order), this reverses the whole array.
        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;
        int j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
}
```
### Algorithm
- 1. Iterate from the second-to-last element (`i = n-2`) towards the beginning of the array. Find the first index `i` where `nums[i] < nums[i+1]`.
- 2. If no such index `i` is found, the entire array is in descending order. This is the largest permutation. Reverse the entire array to get the smallest permutation and finish.
- 3. If an index `i` is found, iterate from the end of the array (`j = n-1`) towards `i`. Find the first index `j` where `nums[j] > nums[i]`.
- 4. Swap the elements at indices `i` and `j`.
- 5. Reverse the subarray from index `i+1` to the end of the array.

# Solutions
### CSharp

```csharp
public class Solution { public void NextPermutation ( int [] nums ) { int n = nums . Length ; int i = n - 2 ; while ( i >= 0 && nums [ i ] >= nums [ i + 1 ]) { -- i ; } if ( i >= 0 ) { for ( int j = n - 1 ; j > i ; -- j ) { if ( nums [ j ] > nums [ i ]) { swap ( nums , i , j ); break ; } } } for ( int j = i + 1 , k = n - 1 ; j < k ; ++ j , -- k ) { swap ( nums , j , k ); } } private void swap ( int [] nums , int i , int j ) { int t = nums [ j ]; nums [ j ] = nums [ i ]; nums [ i ] = t ; } }
```

### Java

```java
import java.util.Arrays ; public class Next_Permutation { // time: O(N^2) // space: O(1) public class Solution { public void nextPermutation ( int [] nums ) { if ( nums == null || nums . length == 0 ) { return ; } // 总体目标是，高位的小数字，换低位的大数字，才能得到next for ( int i = nums . length - 2 ; i >= 0 ; -- i ) { // 3, 4, 5, 2, 1 // 注意. i < Len - 1. 也就是停在倒数第二个 if ( nums [ i ] < nums [ i + 1 ]) { // 第一个波峰波谷 => 4 for ( int j = nums . length - 1 ; j > i ; -- j ) { if ( nums [ j ] > nums [ i ]) { // 找到第一个比nums-i大的数 => 5 swap ( nums , i , j ); // 3,5,4,2,1 // reverse 因为剩下部分肯定是从大到小 // 找到第一个比nums-i大的数的一步，相当于是排序，找insert position reverse ( nums , i + 1 , nums . length - 1 ); // [4,2,1] reverse to [1,2,4] => 3, 5, 1, 2, 4 return ; } } } } reverse ( nums , 0 , nums . length - 1 ); // for没有return，就整个翻转 } private void swap ( int [] nums , int i , int j ) { int tmp = nums [ i ]; nums [ i ] = nums [ j ]; nums [ j ] = tmp ; } private void reverse ( int [] nums , int i , int j ) { while ( i < j ) { int tmp = nums [ i ]; nums [ i ] = nums [ j ]; nums [ j ] = tmp ; i ++; j --; } } } } ////// class Solution { public void nextPermutation ( int [] nums ) { int n = nums . length ; int i = n - 2 ; for (; i >= 0 ; -- i ) { if ( nums [ i ] < nums [ i + 1 ]) { break ; } } if ( i >= 0 ) { for ( int j = n - 1 ; j > i ; -- j ) { if ( nums [ j ] > nums [ i ]) { swap ( nums , i , j ); break ; } } } for ( int j = i + 1 , k = n - 1 ; j < k ; ++ j , -- k ) { swap ( nums , j , k ); } } private void swap ( int [] nums , int i , int j ) { int t = nums [ j ]; nums [ j ] = nums [ i ]; nums [ i ] = t ; } }
```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */ var nextPermutation =
  function (nums) {
    const n = nums.length;
    let i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
      --i;
    }
    if (i >= 0) {
      let j = n - 1;
      while (j > i && nums[j] <= nums[i]) {
        --j;
      }
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    for (i = i + 1, j = n - 1; i < j; ++i, --j) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }
  };

```

### CPP

```cpp
class Solution { public: void nextPermutation ( vector < int >& nums ) { int n = nums . size (); int i = n - 2 ; while ( ~ i && nums [ i ] >= nums [ i + 1 ]) { -- i ; } if ( ~ i ) { for ( int j = n - 1 ; j > i ; -- j ) { if ( nums [ j ] > nums [ i ]) { swap ( nums [ i ], nums [ j ]); break ; } } } reverse ( nums . begin () + i + 1 , nums . end ()); } };
```

### Python

```python
''' >>> i = 3 >>> ~i -4 >>> bool(~i) True ####################### >>> j = -1 >>> ~j 0 >>> bool(~j) False ####################### >>> a = (i for i in range (10, -1, -1) if i < 6) >>> a <generator object <genexpr> at 0x10a17eeb0> >>> next(a) 5 >>> >>> >>> b = (i for i in range (10, -1, -1) if i < 0) >>> next(b) Traceback (most recent call last): File "<stdin>", line 1, in <module> StopIteration >>> next(b, -1) -1 >>> ''' class Solution : def nextPermutation ( self , nums : List [ int ]) -> None : """ Do not return anything, modify nums in-place instead. """ n = len ( nums ) # next(func, -1) => default value -1 i = next (( i for i in range ( n - 2 , - 1 , - 1 ) if nums [ i ] < nums [ i + 1 ]), - 1 ) if i != - 1 : j = next (( j for j in range ( n - 1 , i , - 1 ) if nums [ j ] > nums [ i ])) nums [ i ], nums [ j ] = nums [ j ], nums [ i ] nums [ i + 1 :] = nums [ i + 1 :][:: - 1 ] # wrong reverse: nums[i + 1:] = nums[i + 1::-1] ############## ''' >>> a=[1,2,3] >>> reversed(a) <list_reverseiterator object at 0x108458be0> >>> list(reversed(a)) [3, 2, 1] # but, use reversed(a) to directly assign values is ok >>> b=[4,5,6,7,8] >>> b[:3] = reversed(a) >>> b [3, 2, 1, 7, 8] ''' class Solution : def nextPermutation ( self , nums : List [ int ]) -> None : if not nums : return # 总体目标是，高位的小数字，换低位的大数字，才能得到next for i in range ( len ( nums ) - 2 , - 1 , - 1 ): # 3, 4, 5, 2, 1 if nums [ i ] < nums [ i + 1 ]: # 第一个波峰波谷 => 4 j = next ( j for j in range ( len ( nums ) - 1 , i , - 1 ) if nums [ j ] > nums [ i ]) # 找到第一个比nums-i大的数 => 5 nums [ i ], nums [ j ] = nums [ j ], nums [ i ] # 3,5,4,2,1 # reverse 因为剩下部分肯定是从大到小 # 找到第一个比nums-i大的数的一步，相当于是排序，找insert position nums [ i + 1 :] = reversed ( nums [ i + 1 :]) # [4,2,1] reverse to [1,2,4] => 3, 5, 1, 2, 4 return nums . reverse () # for没有return，就整个翻转 ########### class Solution : def nextPermutation ( self , nums : List [ int ]) -> None : n = len ( nums ) to_left = [ i for i in range ( n - 2 , - 1 , - 1 ) if nums [ i ] < nums [ i + 1 ]] if not to_left : nums = nums [:: - 1 ] return i = max ( to_left ) if i >= 0 : to_right = [ j for j in range ( n - 1 , i , - 1 ) if nums [ j ] > nums [ i ] ] j = to_right [ 0 ] nums [ i ], nums [ j ] = nums [ j ], nums [ i ] nums [ i + 1 :] = nums [ i + 1 :: - 1 ]
```