Previous Permutation With One Swap
MedPrompt
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 <= 1041 <= arr[i] <= 104
Approaches
2 approaches with complexity analysis and trade-offs.
This approach exhaustively tries every possible single swap. For each swap, it checks if the resulting permutation is smaller than the original. Among all such valid smaller permutations, it keeps track of the lexicographically largest one.
Algorithm
- Initialize a variable
bestPermutationto hold the result. Initially, it can be a copy of the original array or a null value. - Generate every possible pair of indices
(i, j)wherei < j. - For each pair, create a new array
currentPermutationby swappingarr[i]andarr[j]. - Check if
currentPermutationis lexicographically smaller than the originalarr. - If it is smaller, compare it with
bestPermutation. IfcurrentPermutationis lexicographically larger thanbestPermutation, updatebestPermutationtocurrentPermutation. - After checking all pairs, if a smaller permutation was found,
bestPermutationwill hold the largest one. Otherwise, it will still be the original array.
Walkthrough
The brute-force method systematically explores all potential solutions. We can iterate through every possible pair of distinct indices (i, j) in the array. For each pair, we perform a swap. This creates a new permutation. We then check if this new permutation is lexicographically smaller than the original array. If it is, we compare it against the best result we've found so far. The 'best' result is the smaller permutation that is lexicographically the largest. We continue this process for all pairs, ensuring we find the optimal one. If no swap results in a smaller permutation, it means the array is already the smallest possible, and we return it unchanged.
class Solution { public int[] prevPermOpt1(int[] arr) { int[] bestPermutation = arr; boolean found = false; for (int i = 0; i < arr.length; i++) { for (int j = i + 1; j < arr.length; j++) { int[] currentPermutation = arr.clone(); swap(currentPermutation, i, j); if (isSmaller(currentPermutation, arr)) { if (!found || isSmaller(bestPermutation, currentPermutation)) { bestPermutation = currentPermutation; found = true; } } } } return bestPermutation; } private void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } private boolean isSmaller(int[] a, int[] b) { for (int i = 0; i < a.length; i++) { if (a[i] < b[i]) return true; if (a[i] > b[i]) return false; } return false; // they are equal }}Complexity
Time
O(N^3). There are O(N^2) pairs to swap. For each swap, copying the array and comparing it takes O(N) time.
Space
O(N), where N is the length of the array. This space is used to store copies of the array for permutations.
Trade-offs
Pros
Simple to conceptualize and implement.
Guaranteed to find the correct answer by checking all possibilities.
Cons
Extremely inefficient due to its cubic time complexity.
Will result in a 'Time Limit Exceeded' error for the given constraints.
A much more efficient approach uses a greedy, single-pass strategy. To get the largest permutation that is smaller than the input, we want to make a change as far to the right as possible. This minimizes the impact on the more significant (left-side) digits. This involves finding a 'pivot' element that can be swapped with a smaller element to its right to create a smaller permutation, while carefully choosing the swap element to ensure the result is as large as possible.
Algorithm
- Step 1: Find Pivot
i: Scan the array from right to left, starting from the second-to-last element. Find the first indexisuch thatarr[i] > arr[i+1]. This is our 'pivot'. If no such index is found, the array is already the smallest permutation, so return it. - Step 2: Find Swap Element
j: Scan the array from right of the pivotito the end. We need to find an elementarr[j]to swap witharr[i]. To make the resulting permutation as large as possible,arr[j]must be the largest value in the suffixarr[i+1...n-1]that is strictly smaller thanarr[i]. To handle duplicates correctly (which would result in an even larger permutation), we must pick the leftmost occurrence of this value. - Step 3: Swap: Swap the elements at index
iand the found indexj. - Step 4: Return: The modified array is the desired result.
Walkthrough
This optimized approach avoids brute force by making intelligent choices based on the properties of lexicographical order.
First, we find the rightmost element arr[i] that is larger than its right neighbor arr[i+1]. This index i is our pivot. Making a swap at this position, while keeping the prefix arr[0...i-1] unchanged, ensures we find a permutation that is just slightly smaller than the original, and it will be larger than any permutation created by a swap at an index less than i. If no such i exists, the array is sorted non-decreasingly (e.g., [1,1,5]), and no smaller permutation is possible.
Second, after finding the pivot i, we must choose an element arr[j] from the suffix arr[i+1...n-1] to swap with arr[i]. To maximize the new permutation, the new arr[i] should be as large as possible, which means we must find the largest value in the suffix that is still smaller than the original arr[i]. We search for this value and its index j.
Finally, we swap arr[i] and arr[j] to get the final result.
class Solution { public int[] prevPermOpt1(int[] arr) { int n = arr.length; if (n <= 1) { return arr; } // Step 1: Find the largest index i such that arr[i] > arr[i+1] int i = n - 2; while (i >= 0 && arr[i] <= arr[i + 1]) { i--; } // If no such index exists, the array is already the smallest permutation if (i < 0) { return arr; } // Step 2: Find the index j of the largest element to the right of i that is smaller than arr[i] // We want the leftmost occurrence of that value to maximize the permutation. int j = i + 1; for (int k = i + 2; k < n; k++) { if (arr[k] < arr[i] && arr[k] > arr[j]) { j = k; } } // Step 3: Swap the elements at i and j int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; }}Complexity
Time
O(N), where N is the length of the array. We perform at most two linear scans of the array.
Space
O(1), as the swap is performed in-place and only a few variables are used for indices.
Trade-offs
Pros
Highly efficient with linear time complexity.
Uses constant extra space.
Optimal solution for the given constraints.
Cons
The logic can be tricky to derive, especially handling duplicate values correctly.
Solutions
Solution
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; }}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; }};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 arrVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.