## DEV Community 👩‍💻👨‍💻 sachin26

Posted on • Updated on

# Striver's SDE Sheet Journey - #3 Next Permutation

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`
output: `nums`

#2

input : `nums`
output: `nums`

## Solution

The following algorithm is presented by a man named Narayan Pandita 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. 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`

step-1 find the first number `pivot` which not increasing in ascending order, from the right side.
from the num 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` 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`, 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--);
}
}
``````