LeetCode 1053. Previous Permutation With One Swap Solution in Java, C++, Python & More | Explanation + Code

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

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] ≠ 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).

PythonJavaC++GoTypeScript

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)