##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1053.html

# 1053. Previous Permutation With One Swap (Medium)

Given an array A of positive integers (not necessarily distinct), return the lexicographically largest permutation that is smaller than A, that can be made with one swap (A swap exchanges the positions of two numbers A[i] and A[j]).  If it cannot be done, then return the same array.

Example 1:

Input: [3,2,1]
Output: [3,1,2]
Explanation: Swapping 2 and 1.


Example 2:

Input: [1,1,5]
Output: [1,1,5]
Explanation: This is already the smallest permutation.


Example 3:

Input: [1,9,4,6,7]
Output: [1,7,4,6,9]
Explanation: Swapping 9 and 7.


Example 4:

Input: [3,1,1,3]
Output: [1,3,1,3]
Explanation: Swapping 1 and 3.


Note:

1. 1 <= A.length <= 10000
2. 1 <= A[i] <= 10000

Related Topics:
Array, Greedy

## Solution 1.

• class Solution {
public int[] prevPermOpt1(int[] A) {
PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>((a, b) -> (a[0] - b[0]));
int swapIndex = -1;
int swapNum = 0;
int length = A.length;
for (int i = length - 1; i > 0; i--) {
int num = A[i];
priorityQueue.offer(new int[]{num, i});
if (num < A[i - 1]) {
swapIndex = i - 1;
swapNum = A[i - 1];
break;
}
}
if (swapIndex < 0)
return A;
int nextSwapNum = 0, nextSwapIndex = -1;
while (!priorityQueue.isEmpty() && priorityQueue.peek()[0] < swapNum) {
int[] numIndex = priorityQueue.poll();
nextSwapNum = numIndex[0];
nextSwapIndex = numIndex[1];
}
A[swapIndex] = nextSwapNum;
A[nextSwapIndex] = swapNum;
return A;
}
}

############

class Solution {
public int[] prevPermOpt1(int[] arr) {
int n = arr.length;
for (int i = n - 1; i > 0; --i) {
if (arr[i - 1] > arr[i]) {
for (int j = n - 1; j > i - 1; --j) {
if (arr[j] < arr[i - 1] && arr[j] != arr[j - 1]) {
int t = arr[i - 1];
arr[i - 1] = arr[j];
arr[j] = t;
return arr;
}
}
}
}
return arr;
}
}

• // OJ: https://leetcode.com/problems/previous-permutation-with-one-swap/
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
vector<int> prevPermOpt1(vector<int>& A) {
int first = -1, second;
for (int i = A.size() - 1; i > first; --i) {
while (i - 1 > first && A[i - 1] == A[i]) --i;
int j = i - 1;
while (j > first && A[j] <= A[i]) --j;
if (j > first) {
first = j;
second = i;
}
}
if (first > -1) swap(A[first], A[second]);
return A;
}
};

• class Solution:
def prevPermOpt1(self, arr: List[int]) -> List[int]:
n = len(arr)
for i in range(n - 1, 0, -1):
if arr[i - 1] > arr[i]:
for j in range(n - 1, i - 1, -1):
if arr[j] < arr[i - 1] and arr[j] != arr[j - 1]:
arr[i - 1], arr[j] = arr[j], arr[i - 1]
return arr
return arr

############

# 1053. Previous Permutation With One Swap
# https://leetcode.com/problems/previous-permutation-with-one-swap/

class Solution:
def prevPermOpt1(self, arr: List[int]) -> List[int]:
n = len(arr)
if n <= 1: return arr

index = -1
for i in range(n - 1, 0, -1):
if arr[i] < arr[i - 1]:
index = i - 1
break

if index == -1: return arr
for i in range(n - 1, index - 1, -1):
if arr[i] < arr[index] and arr[i] != arr[i - 1]:
arr[i], arr[index] = arr[index], arr[i]
break

return arr


• func prevPermOpt1(arr []int) []int {
n := len(arr)
for i := n - 1; i > 0; i-- {
if arr[i-1] > arr[i] {
for j := n - 1; j > i-1; j-- {
if arr[j] < arr[i-1] && arr[j] != arr[j-1] {
arr[i-1], arr[j] = arr[j], arr[i-1]
return arr
}
}
}
}
return arr
}

• function prevPermOpt1(arr: number[]): number[] {
const n = arr.length;
for (let i = n - 1; i > 0; --i) {
if (arr[i - 1] > arr[i]) {
for (let j = n - 1; j > i - 1; --j) {
if (arr[j] < arr[i - 1] && arr[j] !== arr[j - 1]) {
const t = arr[i - 1];
arr[i - 1] = arr[j];
arr[j] = t;
return arr;
}
}
}
}
return arr;
}