Algorithm
Problem Name: 1053. Previous Permutation With One Swap
Given an array of positive integers arr (not necessarily distinct), return the
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 <= 1041 <= arr[i] <= 104
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const prevPermOpt1 = function(A) {
let n = A.length, left = n - 2, right = n - 1;
while (left >= 0 && A[left] < = A[left + 1]) left--;
if (left < 0) return A;
while (A[left] < = A[right]) right--;
while (A[right - 1] == A[right]) right--;
swap(A,left,right)
return A;
};
function swap(a, i, j) {
let tmp = a[i]
a[i] = a[j]
a[j] = tmp
}
Input
arr = [3,2,1]
Output
[3,1,2]
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def prevPermOpt1(self, A: List[int]) -> List[int]:
pre = []
for i in range(len(A) - 1, -1, -1):
bisect.insort_left(pre, (A[i], i))
if pre.index((A[i], i)):
j = pre[pre.index((A[i], i)) - 1][1]
A[i], A[j] = A[j], A[i]
break
return A
Input
arr = [3,2,1]
Output
[3,1,2]