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[1324]
output: nums[1342]

#2

input : nums[2431]
output: nums[3124]

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