The permutation to be returned should have two characteristics:
- It should be smaller than A: Clearly, if A is the smallest possible permutation, i.e., the numbers in the array are arranged in ascending order then we have to return A itself (eg: [1,2,4,8]). Else, we have to swap a digit X at a more significant position than a digit Y where X>Y. This will lead to a smaller permutation. For example, swapping 4 and 1 in the array [2,4,3,1] will lead to a smaller permutation.
- It should be the biggest such permutation possible: As the resulting permutation should be the biggest possible and yet smaller than A, we need to find the least significant (right-most) number which we can swap with a smaller number to its right. This will lead to the biggest such answer possible. For example, consider the input [2,4,3,1] again. The right-most number which can be swapped with a number smaller than that on its right is 3 (swapped with 1) which leads to [2,4,1,3]. The other alternatives which lead to a permutation smaller than A are [2,3,4,1], [2,1,3,4], [1,4,3,2]. Note that all these permutations are smaller than the [2,4,1,3].
Suppose the array is [a_1,a_2,a_3,…,a_n]. Assuming a_j to be the right-most number which can be swapped. It is clear that numbers a_j+1, a_j+2, ..., a_n will follow the property a_j+1<=a_j+2<=...<=a_n, i.e., they will be in increasing order (seen left-to-right) because even if one such number were to violate this property, we would have chosen that number to swap with a smaller number on its right. Further, since we want the resulting number to be the biggest such possible number, we want to swap a_j with a the biggest number possible on its right which is smaller than a_j so we will iterate i from n to j+1 and swap a_j with a_i as soon as we find a_i>a_j. Let’s consider two examples:
Example 1: No duplicates
A=[9,8,5,1,2,3,4,6]
Here, a_j = 5. See that [1,2,3,4,6] is in increasing order so swapping any pair would lead to a permutation larger than A.
Now, we swap 5 with 4 to get the answer [9,8,4,1,2,3,5,6]. Note that swapping 5 with any other smaller number to its right would have led to a smaller permutation as then a smaller number would have taken the place of 5, eg: [9,8,1,5,2,3,4,6].
Example 2: With duplicates
A=[9,8,7,7,7,1,1,2,3,4,4,4,10]
Here, to get the maximum possible permutation smaller than A, we have to swap the least significant (rightmost) occurrence of 7 with the most significant (leftmost) occurrence of 4. So answer would be: [9,8,7,7,4,1,1,2,3,7,4,4,10]. Consider any other swap, say [9,8,7,4,7,1,1,2,3,7,4,4,10], it leads to a permutation smaller than the one above as 4 goes to a more significant position or 7 comes to a less significant position (eg: [9,8,7,7,4,1,1,2,3,4,7,4,10]).
The code is straightforward and contains some explanation:
vector<int> prevPermOpt1(vector<int>& A) {
int idx = -1;
// find the right-most number which can be swapped with a number smaller than that to its right
for (int i=A.size()-1; i>0; i--) {
if (A[i]<A[i-1]) {
idx = i-1;
break;
}
}
// array already sorted so permutation is minimum number
if (idx == -1) return A;
// find the most significant occurrence of the largest number to swap it with
for (int i=A.size()-1; i>idx; i--) {
// handle duplicates as we need the most significant occurrence
if (A[i] == A[i-1])
continue;
if (A[i]<A[idx]) {
swap(A[i], A[idx]);
break;
}
}
return A;
}
Time complexity: O(n)