Skip to content

1053. Previous Permutation With One Swap

SourceWeekly Contest 138 Q3DifficultyMediumRating1633

Description

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

Solutions

Solution 1: Greedy

Thinking

A single swap must produce the lexicographically largest permutation that is still smaller. The first descent \(arr[i-1]>arr[i]\) from the right is the value that should become something smaller on its right.

The replacement should be the largest right-hand value below \(arr[i-1]\); ties take the leftmost copy, so a right-to-left scan skips a value equal to its predecessor.

Swap and return; if there is no descent the array is already minimal.

First, we traverse the array from right to left, find the first index \(i\) that satisfies \(arr[i - 1] > arr[i]\), then \(arr[i - 1]\) is the number we need to swap. Next, we traverse the array from right to left again, find the first index \(j\) that satisfies \(arr[j] < arr[i - 1]\) and \(arr[j] \neq arr[j - 1]\). Now, we swap \(arr[i - 1]\) and \(arr[j]\) and return the array.

If we traverse the entire array and do not find an index \(i\) that meets the conditions, it means the array is already the smallest permutation, so we just return the original array.

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& arr) {
        int n = arr.size();
        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]) {
                        swap(arr[i - 1], arr[j]);
                        return arr;
                    }
                }
            }
        }
        return arr;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
}

Comments