HiπDevs.

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

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

##
*Solution*

*Solution*

The following algorithm is presented by a man named *Narayan Pandita* in the 14th century.

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

before understanding this algo, lets see below pic.

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

```
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--);
}
}
```

## Top comments (0)