Our April 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career

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.

Input: [1, 3, 2]

Output: [2, 1, 3]

Input: [2, 2, 1]

Output: [1, 2, 2]

● 1

● 0

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

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.

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!).

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!).

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!)

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.

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).

O(1).

We used a constant amount of additional memory.

O(n).

Memory used for input = O(n)

Memory used for output = O(n)

Auxiliary space = O(1)

Total space complexity = O(n)