Find the next highest permutation of an array

Problem:

Given an integer array , find the next highest permutation of the numbers.

If the next highest permutation is not found return the smallest permutation of the given input.

Permutation of a number is all possible combinations of the given numbers.

For example,

Given the array:

[1,2,3]

The possible permutations are

[1,3,2] , [2,1,3], [2,3,1] , [3,1,2] , [3,2,1] along with [1,2,3]

Next highest permutation is the next highest number to the given combined number.

So if the elements are [1,2,3]

If you combine them it gives the number 123

Find the next highest number to this number among the possible permutations.

It is 132,

So the output is [1,3,2]

You cannot consider [2,1,3] or any other combinations because these are all greater than 123 but greater than 132 as well.

We want the least number which is higher than the given number.

In case you can’t find the next highest permutation , then return the lowest number possible out of the given input.

For example,

Consider :

[3,2,1]

There is no higher number that is possible with the given numbers.

All other combinations are less than this number.

So return the lowest number which is :

[1,2,3]

Try out the solution here:

https://leetcode.com/problems/next-permutation/

Solution:

If you notice the last example given above [3,2,1]

The numbers are in descending order.

If you take any combination in descending order you can’t find the next highest since they represent the highest number.

So at least one of the digits should be in non decreasing order to find out the next permutation.

Find that first non decreasing number.

This has to be found out by scanning from the right.

Once you find that number, you can find the next possible number.

How to find this?

Keep looking for a number greater than this number to its right.

When you find it , just swap it to this number.

All right ,

We have done two things so far:

• Find the first non decreasing number (scan from the right to find this – so from the right it is the first non increasing number)
• Swap this number with a number greater than this number (the least greatest)

Once we do these two steps, we still need to do one more thing.

Since the rest of the numbers are in descending order , they don’t represent the least highest number.

The least highest number can be found out by reversing the remaining digits.

So reverse the remaining numbers.

The final number is the output we want.

Here is an excellent animation from leetcode.com:

So the algorithm is:

• Find the first non increasing number from the right
• Find the element which is greater than this number to its right
• Swap these elements
• Reverse all the elements next to the swapped position.

Here is the code:

class Solution {
    public void nextPermutation(int[] nums) {
        
        
       //find first non decreasing number
        
        int index = nums.length -2;
        
        
        
        while(index >=0 && nums[index+1] <= nums[index]){
            
            index--;
        }
        
        //find first number greater than this number
        if(index >=0){
            
        int j = nums.length - 1;
         
            while(nums[j] <= nums[index]){
                
                j--;
            }
            
            //swap
            int t = nums[index];
            nums[index] = nums[j];
            
            nums[j] = t;
            
            
            
        }
        
        
        //reverse all digits to its right
        
        int start = index+1;
        
        int last = nums.length - 1;
        
        
        while(start < last){
            
            
            int temp = nums[start];
            nums[start] = nums[last];
            nums[last] = temp;
            
            start++;
            last--;
        }
        
    }
}

But what about the worst scenario?

We don’t find the next possible higher permutation.

In this case we need to return the lowest possible permutation.

Remember that the case where the next possible higher permutation is not possible is when the numbers are in descending order.

Like this:

[5, 4, 3, 2, 1]

So all you have to do in this case is reverse the digits.

This is taken care of by the last step in the above code.

So you don’t have to write any extra logic to deal with this!

Time complexity:

We do a single pass along the array so time complexity is O(n)

Space complexity:

We solve in place without any extra space so space complexity is O(1)

That’s it!