Next Permutation in bits 😉

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

The next permutation of an array of integers is the next lexicographically greater permutation of its integer.

lexicographically, is a method used in dictionaries, ex: acbd, next permutation will be adbc

More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged in the lowest possible order (i.e., sorted in ascending order).

• Input: nums = [1,2,3] | Output: [1,3,2]
• Input: nums = [3,2,1] | Output: [1,2,3]

Let's Start 🙌

On seeing the question you might think we have to find all the possible permutations out of which then, find the next permutation array came after the given array like this below:

All permutations of {1,2,3} are {{1,2,3} , {1,3,2}, {2,1,3} , {2,3,1} , {3,1,2} , {3,2,1}}. So, the next permutation just after {1,3,2} is {2,1,3}.

• But this is not a good method for the approach, just sit back and see what you have to return. Is there any possible pattern you can work on?

• Right, if you had to find out it's great 👌.

• You have to find the value in the next permutation array to return, must be lower and breaks the rule of descending order starting after it, let's see the example 🤨.

1. [ 2, 2, 5, 2, 4, 3, 1 ], NEXT PERMUTATION??

2. from last, you can see the arr.size() < arr.size()-i, but at index [ 3 ] it neglects the pattern.

int startPivot = -1, i;

        for(i = nums.size()-1; i>0; i--){
            if(nums[i]>nums[i-1]){
                startPivot = nums[i-1];
                break;
            }
        }

1. A pointer at the index [ 3 ], to find out the next big number i.e 3.

2. Replace index [ 3 ] with index [ 5 ], [ 2, 2, 5, 3, 4, 2, 1 ].

3. Now reverse the array from the index [ 3 + 1] and [ arr.size()-1 ].

if(startPivot>=0){
    for(int j = nums.size()-1; j>=i; j--){
          if(startPivot<nums[j]){
              swap(nums[i-1],nums[j]);
              reverse(nums.begin() + i, nums.end());
              break;
          }
     }
}

[ 2, 2, 5, 3, 1, 2, 4] and here you got the next permutation.

• But what if there is no exception where arr.size() < arr.size()-1.
• we just have to reverse the array [ 5, 4, 3, 2, 1 ] -> [ 1, 2, 3, 4, 5 ].

else{
            reverse(nums.begin(), nums.end());
}

Solution

class Solution {
public:
    void nextPermutation(vector<int>& nums) {

        int startPivot = -1, i;

        for(i = nums.size()-1; i>0; i--){
            if(nums[i]>nums[i-1]){
                startPivot = nums[i-1];
                break;
            }
        }


        if(startPivot>=0){
            for(int j = nums.size()-1; j>=i; j--){
                if(startPivot<nums[j]){
                    swap(nums[i-1],nums[j]);
                    reverse(nums.begin() + i, nums.end());
                    break;
                }
            }
        }
        else{
            reverse(nums.begin(), nums.end());
        }

    }
};

Thanks for reading ❤, Leetcode question here