Given a sequence, return its next lexicographically greater permutation. If such a permutation does not exist then return it in ascending order. 

Try to solve the problem with a constant amount of additional memory. 

Example One

Input: [1, 3, 2]

Output: [2, 1, 3]

Example Two

Input: [2, 2, 1]

Output: [1, 2, 2]

Constraints:

● 1

● 0

‍

Solutions

We provided two solutions. Let us assume that n is the size of the sequence.

1) brute_force_solution.cpp

First, We need to generate all the permutations of the given array but before that, we need to create a copy of it so that we have the original permutation because we will need it later to compare with each possible permutation of the array. 

1. Sort the array.

2. Generate permutations in the lexicographic order.

3. Compare the generated permutations to the original permutation of the given array.

4. When both permutations become equal, skip all equal permutations of original permutation.

5. After skipping equal permutations, get the next greater permutation. 

Time Complexity:

O(n * n!).

Sorting array of size n will take O(n * log n) time. There are n! possible permutations of the array of size n. Generating all of them will contribute O(n!) to time complexity. Now, we have n! permutations each of size n. Comparing given permutation to each of permutation will add O(n * n!) to time complexity. Hence, our overall time complexity will be O(n * n!).

Auxiliary Space Used:

O(n * n!).

Creating a copy of the original array will take O(n) space. We are storing all permutations of the array of size n. There are n! possible permutations and each of size n. Hence auxiliary space used by brute force approach is O(n * n!).

Space Complexity:

O(n * n!).

Memory used for input = O(n)

Memory used for output = O(n)

Auxiliary space = O(n * n!)

Total space complexity = O(n * n!)

// -------- START --------

void generate_all_permutations(vector arr, vector> &permutations, int index)
{
    if (index == arr.size())
    {
        permutations.push_back(arr);
        return;
    }

    // Swap all of the values from greater or equal indices to 'index' to generate all possible permutations.
    for (int i = index; i < arr.size(); i++)
    {
        swap(arr[i], arr[index]);
        generate_all_permutations(arr, permutations, index + 1);
        swap(arr[i], arr[index]);
    }
}

vector next_permutation(vector arr)
{
    vector> all_permutations;

    vector dupArr(arr.begin(), arr.end());

    sort(dupArr.begin(), dupArr.end());

    generate_all_permutations(dupArr, all_permutations, 0);

    int total_permutations = all_permutations.size();
    for (int i = 0; i < total_permutations; i++)
    {
        if (all_permutations[i] == arr)
        {
            /**
             * The given array can have duplicates but our algorithm does not take that into consideration.
             * So the same permutation can appear more than once while generating all of the permutations.
             * Hence, we need to skip such equal permutations.
             */
            while (i < total_permutations && all_permutations[i] == arr)
            {
                i++;
            }
            arr = all_permutations[i % total_permutations];
            break;
        }
    }
    return arr;
}

// -------- END --------

2) optimized_solution.cpp

We will move step by step with an example of n = 6, array = [1, 4, 6, 5, 3, 2].

● A greater permutation than the current permutation can be formed only if there exists an element at index i which is strictly smaller than an element at index j where i < j. For example:

○ We can get a greater permutation if we swap the values at index 0 with any value at index between 1 to 5. If we swap the value at index 0 with the value at index 5, we get the permutation [2, 4, 6, 5, 3, 1] which is a greater permutation than the permutation [1, 4, 6, 5, 3, 2].

○ We also can get a greater permutation by swapping the value at index 1 with the values at indices 2 and 3.

● In order to get the lexicographically next permutation, we need to modify the smallest suffix which has the above property when considered as an independent sequence. Let us assume that the smallest suffix which has the above property starts at index i. We have two indices for the possible value of i for the given example. They are 0 and 1. Finding the value of i is trivial and left as an exercise to the reader.

● After finding i, which in our case is equal to 1, we need to find the last index j in [i+1 … n] such that array[i] < array[j]. In our example, j equals 3. We will now swap the values at index i and j.

● After swapping the values at i and j, the array becomes [1, 5, 6, 4, 3, 2] which is a greater permutation than [1, 4, 6, 5, 3, 2]. But there are few other permutations which lie between [1, 4, 6, 5, 3, 2] and [1, 5, 6, 4, 3, 2].

● The way we picked i and j ensures that after swapping i and j, all of the following statements hold:

○ We will get a permutation larger than the initial one.

○ The longest possible prefix of the array will remain unmodified.

○ The smallest possible number will be placed at index j after swapping.

○ The number in the indices between i+1 to n-1 will remain sorted in non-increasing order.

● After replacing the value at index i with a greater number from index j, we can shuffle the numbers between the indices i+1 to n-1 and still get a larger permutation than the initial one. The permutation where the numbers from i+1 to n-1 are sorted in non-decreasing order is indeed the smallest one among them. Now as the segment is sorted in non-increasing order, we will just reverse it as the last step of the algorithm.

● After reversing array[i+1 … n], the array becomes [1, 5, 2, 3, 4, 6] which is the next permutation for the initial array.

Time Complexity:

O(n).

Finding index i contributes to O(n) time complexity. Finding index j may take O(n) time. Reversing the array contributes O(n) time. Hence, our overall time complexity becomes O(n).

Auxiliary Space Used:

O(1).

We used a constant amount of additional memory. 

Space Complexity:

O(n).

Memory used for input = O(n)

Memory used for output = O(n)

Auxiliary space = O(1)

Total space complexity = O(n)

‍

// -------- START --------

vector next_permutation(vector arr)
{
    if (arr.size() < 2)
    {
        return arr;
    }

    int n = arr.size();
    int index;
    for (index = n - 1; index > 0; index--)
    {
        if (arr[index] > arr[index - 1])
        {
            break;
        }
    }

    /**
     * The value of index being equal to zero implies that the array is sorted in non-increasing order.
     * Reversing the array will sort the array in ascending order.
     */
    if (index == 0)
    {
        reverse(arr.begin(), arr.end());
        return arr;
    }

    // Find the smallest number which is greater than the pivot element and swap them.
    int pivotIndex = index - 1;
    while (index < n && arr[index] > arr[pivotIndex])
    {
        index++;
    }
    swap(arr[pivotIndex], arr[index - 1]);

    reverse(arr.begin() + pivotIndex + 1, arr.end());
    return arr;
}

// -------- END --------