12.Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory. Find the next greater element if possible from the same digits.

Example 1:
Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:
Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:
Input: nums = [1,1,5]
Output: [1,5,1]

Example 4:
Input: nums = [1]
Output: [1]

Solution I:

Algorithm:

• Traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. For example, if the input number is “534976”, we stop at 4 because 4 is smaller than next digit 9. If we do not find such a digit, then output is “Not Possible”.

• Now search the right side of above found digit ‘d’ for the smallest digit greater than ‘d’. For “534976″, the right side of 4 contains “976”. The smallest digit greater than 4 is 6.

• Swap the above found two digits, we get 536974

• Now sort all digits from position next to ‘d’ to the end of number. The number that we get after sorting is the output. For above example, we sort digits in bold 536974. We get “536479”.

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

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

        if (idx != -1)
        {

            int idx2 = idx + 1;

            for (int i = idx + 1; i < nums.size(); i++)
            {

                if (nums[i] > nums[idx] && nums[i] < nums[idx2])
                {
                    idx2 = i;
                }
            }

            swap(nums[idx], nums[idx2]);
            sort(nums.begin() + idx + 1, nums.end());
        }
        else
        {
            sort(nums.begin(), nums.end());
        }
    }
};

Time Complexity: O(n log n)

Solution II:

Instead of doing simple sort, We know that all digits are linearly sorted in reverse order. So we need to reverse the digits to get the array sorted.

class Solution
{
public:
    void reverse(vector<int> &nums, int start)
    {
        int end = nums.size() - 1;

        while (start <= end)
        {
            if (nums[start] > nums[end])
            {
                swap(nums[start], nums[end]);
            }
            start++;
            end--;
        }
        
        return;
    }
    
    void nextPermutation(vector<int> &nums)
    {

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

        if (idx != -1)
        {

            int idx2 = idx + 1;

            for (int i = idx + 1; i < nums.size(); i++)
            {

                if (nums[i] > nums[idx] && nums[i] <= nums[idx2])
                {
                    idx2 = i;
                }
            }

            swap(nums[idx], nums[idx2]);
            reverse(nums, idx + 1);
        }
        else
        {
            reverse(nums, 0);
        }
    }
};

Time Complexity: O(n)