Problem
Given an array of positive integers arr
(not necessarily distinct), return the lexicographically largest permutation that is smaller than arr
, that can be made with exactly one swap. If it cannot be done, then return the same array.
Note that a swap exchanges the positions of two numbers arr[i]
and arr[j]
Example 1:
Input: arr = [3,2,1]
Output: [3,1,2]
Explanation: Swapping 2 and 1.
Example 2:
Input: arr = [1,1,5]
Output: [1,1,5]
Explanation: This is already the smallest permutation.
Example 3:
Input: arr = [1,9,4,6,7]
Output: [1,7,4,6,9]
Explanation: Swapping 9 and 7.
Constraints:
1 <= arr.length <= 104
1 <= arr[i] <= 104
Solution
/**
* @param {number[]} arr
* @return {number[]}
*/
var prevPermOpt1 = function(arr) {
for (var i = arr.length - 2; i >= 0; i--) {
if (arr[i] <= arr[i + 1]) continue;
var max = 0;
var maxIndex = -1;
for (var j = i + 1; j < arr.length; j++) {
if (arr[j] > max && arr[j] < arr[i]) {
max = arr[j];
maxIndex = j;
}
}
swap(arr, i, maxIndex);
break;
}
return arr;
};
var swap = function(arr, i, j) {
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
};
Explain:
- we need a smaller array than the current one, so that we need to swap a smaller number from right to left
- we need a largest array from all the possible result, so that we are going to find the first possible index to swap, from the right of array
- from right find a possible index to swap, find biggest number smaller than this one to swap on the right
Complexity:
- Time complexity : O(n).
- Space complexity : O(1).
Solution 2
/**
* @param {number[]} arr
* @return {number[]}
*/
var prevPermOpt1 = function(arr) {
for (var i = arr.length - 2; i >= 0; i--) {
if (arr[i] <= arr[i + 1]) continue;
for (var j = arr.length; j > i; j--) {
if (arr[j] < arr[i] && arr[j] !== arr[j - 1]) {
swap(arr, i, j);
return arr;
}
}
}
return arr;
};
var swap = function(arr, i, j) {
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
};
Explain:
because we know that numbers from right to left is in order, (from solution 1), we can just find the first one from right.
Complexity:
- Time complexity : O(n).
- Space complexity : O(1).