Next Permutation - O(n) Solution

Problem Description

🔗 Link to Question: Next Permutation | Practice | GeeksforGeeks

Implement the next permutation, which rearranges the list of numbers into Lexicographically next greater permutation of list of numbers. If such arrangement is not possible, it must be rearranged to the lowest possible order i.e. sorted in an ascending order. You are given an list of numbers arr[ ] of size N.

Brute Force and STL Approach

• The brute force approach would be to enumerate all the permutations and store them in a list in sorted order. Then we can look for the given “permutation” and return the next permutation in the list. If our permutation is the last one, then return the first permutation. This is an O(n*n!) time complexity approach with space complexity of O(n!) too. This is not the desired approach!
• If you know, C++ STL has a function next_permutation(nums.begin(), nums.end()); to find the next permutation of given array in-place. The time complexity of this function is O(n) with a space complexity of O(1).
  • The Interviewer will ask you to implement this function when you present this solution! Let’s do that.

Optimal Approach

• Traverse the array from right.
• Once, we find 'i' such that A[i] > A[i-1],The sub-array A[i...n-1] is in DSC order and
  • To get next permutation:
  • Swap A[i-1] with element just larger than it from A[i...n-1].
  • Sort A[i...n-1]
• After swapping A[i-1] with an element just larger than it from A[i...], DSC order is maintained.
• Sorting an array in DSC order is as good as reversing it.

Consider, an example when n=4. The following image demonstrates WHY the algorithm works.

Code

class Solution{
public:
    vector<int> nextPermutation(int n, vector<int> arr){
        int idx = n-1;

        //Find the breaking point
        while(idx > 0 && arr[idx-1] >= arr[idx])
            idx--;

        //'arr' is not the last permuation for these numbers
        if(idx > 0)
        {
            //Swap arr[idx-1] with just greater element than it from
            //arr[idx...n-1)
            int j=n-1;
            while(j>=idx && arr[j] <= arr[idx-1])
                j--;
            swap(arr[j], arr[idx-1]);
        }
        //idx == 0, if arr was the last permuation for these  numbers

        //reverse the portion, arr[idx...n-1]
        reverse(arr.begin() + idx, arr.end());

        return arr;

    }
};

Complexity Analysis

• Time: $O(n)$
• Space: $O(1)$