Previous Permutation With One Swap

LeetCode Q 1053 - Previous Permutation With One Swap

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 <= A.length <= 10000
• 1 <= A[i] <= 10000

Solution

Code:

public int[] prevPermOpt1(int[] A) {

	if (A == null || A.length <= 1) return A;

	int left = A.length - 2, right = A.length - 1; 

	// find the digit we can swap, i.e. A[left] > A[left + 1]
	while (left >= 0 && A[left] <= A[left - 1]) left--;

	//if the array from right to left is in the descending order we cannot find its previous permutation, we should return itself.
	if (left == 0) return A;

	// find the digit which we should swap with A[left], i.e. find num which is less than A[left] from right to left;
	while (right > left && A[right] >= A[left]) right--;

	while (right >= 1 && A[right - 1] == A[right]) right--;

	// swap
	int temp = A[left];
	A[left] = A[right];
	A[right] = temp;

	return A;
}