Daily Dose of DSA - Day 13

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

Approach :

Step 1: Linearly traverse array from backward such that ith index value of the array is less than (i+1)th index value. Store that index in a variable.

Step 2: If the index value received from step 1 is less than 0. This means the given input array is the largest lexicographical permutation. Hence, we will reverse the input array to get the minimum or starting permutation. Linearly traverse array from backward. Find an index that has a value greater than the previously found index. Store index is another variable.

Step 3: Swap values present in indices found in the above two steps.

Step 4: Reverse array from index+1 where the index is found at step 1 till the end of the array.

class Solution
{
public:
    void nextPermutation(vector<int> &nums)
    {
        next_permutation(nums.begin(), nums.end());
    }
};

class Solution
{
public:
    void nextPermutation(vector<int> &nums)
    {
        int n = nums.size(), k, l;
        for (k = n - 1; k > 0; k--)
        {
            if (nums[k - 1] < nums[k])
            {
                break;
            }
        }

        if (k < 1)
        {
            reverse(nums.begin(), nums.end());
        }

        else
        {
            for (l = n - 1; l > k - 1; l--)
            {
                if (nums[l] > nums[k - 1])
                {
                    break;
                }
            }

            swap(nums[k - 1], nums[l]);
            reverse(nums.begin() + k, nums.end());
        }
    }
};