Striver's SDE Sheet Journey - #3 Next Permutation
Tags: programming, beginners, java, computerscience
Published: 2021-12-18 11:31:15

Hi👋Devs.

Today we will understand the 3rd problem from the SDE-Sheet which is the **Next Permutation**.

## [#3 Next Permutation ](https://leetcode.com/problems/next-permutation/)

In this problem, we have given an int array. we have to rearrange the array in the form of the **next greater permutation** in lexicographically or dictionary order.

> Examples

**#1**

_input_ : `nums[1324]`
_output_: `nums[1342]`

**#2**

_input_ : `nums[2431]`
_output_: `nums[3124]`

## <u>_Solution_</u>

The following algorithm is presented by a man named [_Narayan Pandita_](https://en.wikipedia.org/wiki/Permutation#:~:text=after%20a%20given-,permutation,-.%20It%20changes%20the) in the 14th century.

1. Find the largest index k such that nums[k] < nums[k + 1]. If no such index exists, just reverse nums and done.
2. Find the largest index l > k such that nums[k] < nums[l].
3. Swap nums[k] and nums[l].
4. Reverse the sub-array nums[k + 1:].

before understanding this algo, lets see below pic.


![next permutations of 1234](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/776siv46xzi24s0h1gjp.png)

from the above image, you can get a pretty good idea about what is exactly the next greater permutation and you can also observe the patterns.

lets understand the algo above one in a clear way with an example.

`input : num[1432]`

**step-1** find the first number `pivot` which not increasing in ascending order, from the right side.
_from the num[1432] array, **1** is the number that is not increasing in ascending order_


**step-2** if the `pivot` is not found, all numbers are in ascending order from the right side, which means the given permutation is the last permutation. then reverse the whole array and return.

**step-3** if the first number `pivot` is found, find the exact largest number than the first number `pivot` from the right side.
_from the `num[1432]` array the exact largest number of `pivot=1` is **2**_


**step-4** swap the `pivot` number with its exact largest one.
_after the swap, the array looks like this `num[**2**43**1**]`_


**step-5** reverse the array from the `pivot+1`.
_after reversed, the array looks like this `num[2134]`, which is the exact next greater permutation_

> _Java_

```java
class Solution {
    public void nextPermutation(int[] nums) {
        int pivotIndex;
        int newPivotIndex = 0;
        int arrSize = nums.length;
        
        // find the number which not in ascending order
        for(pivotIndex = arrSize-2; pivotIndex>=0; pivotIndex--){
            
            if(nums[pivotIndex] < nums[pivotIndex+1]) break;
        }
        
        // if all nums are in non-ascending order, then reverse the array
        if(pivotIndex == -1){
            reverse(nums,0,arrSize-1);

        }else{
            // find the exact greater number than pivot
            for(int i=arrSize-1; i>pivotIndex; i--){
                if(nums[i] > nums[pivotIndex]){
                   newPivotIndex = i;
                    break;
                }               
            }    
            
             // swap pivotIndex and newPivotIndex, reverse the array
              swap(nums,pivotIndex,newPivotIndex);
              reverse(nums,pivotIndex+1,arrSize-1);
        }                   
    }
    
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    
    private void reverse(int[] arr, int i, int j) {
        while(i < j) swap(arr, i++, j--);
    }
}
```