LeetCode 1053 - Previous Permutation With One Swap
The problem asks us to find the lexicographically largest permutation that is still smaller than the given array, using exactly one swap operation.
Difficulty: 🟡 Medium
Topics: Array, Greedy
Solution
Problem Understanding
The problem asks us to find the lexicographically largest permutation that is still smaller than the given array, using exactly one swap operation.
A permutation is considered lexicographically smaller if, at the first position where two arrays differ, the new array has a smaller value. For example:
[3,1,2]is smaller than[3,2,1]because at index1,1 < 2[1,7,4,6,9]is smaller than[1,9,4,6,7]because at index1,7 < 9
The important part is that we do not want just any smaller permutation. We want the largest possible one among all smaller permutations obtainable with one swap.
The input array can contain duplicate values, which introduces an important complication. If we swap with the wrong duplicate occurrence, we may produce a smaller permutation than necessary.
The constraints are:
1 <= arr.length <= 10^41 <= arr[i] <= 10^4
Since the array length can be as large as 10^4, an algorithm worse than quadratic time becomes risky. We should aim for an O(n) or O(n log n) solution.
Several edge cases are important:
- The array may already be the smallest possible permutation, such as
[1,1,5] - The array may contain duplicates
- The decreasing point may appear near the beginning or near the end
- Choosing the wrong duplicate element to swap can produce a non optimal answer
The key challenge is finding the single swap that decreases the permutation as little as possible while still making it smaller.
Approaches
Brute Force Approach
A brute force solution would try every possible pair of indices (i, j) where i < j, swap the elements, and check whether the resulting array is lexicographically smaller than the original.
Among all valid smaller permutations, we would keep the largest one.
This approach is correct because it exhaustively evaluates every possible one swap permutation. Since every legal swap is considered, the optimal answer cannot be missed.
However, the time complexity is expensive. There are O(n^2) possible swaps, and comparing permutations costs O(n). That leads to an overall complexity of O(n^3).
With n = 10^4, this is far too slow.
Optimal Greedy Approach
The important observation is that lexicographical order is dominated by the earliest differing position.
To create the largest permutation that is still smaller than the original array:
- We should modify the array as far to the right as possible
- At that position, we should decrease the value by the smallest amount possible
This is very similar to finding the "previous permutation".
We scan from right to left looking for the first index i where:
arr[i] > arr[i + 1]
This identifies the first place where we can make the permutation smaller.
Once we find such an index:
- We must swap
arr[i]with the largest value to its right that is still smaller thanarr[i] - If duplicates exist, we should choose the leftmost occurrence among equal candidates
The duplicate handling is subtle but critical. Swapping with the leftmost duplicate gives the lexicographically largest result.
This greedy strategy works in linear time.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n³) | O(n) | Try every swap and compare all permutations |
| Optimal | O(n) | O(1) | Greedy scan from right to left |
Algorithm Walkthrough
- Start scanning from the second to last element toward the beginning of the array.
We look for the first index i such that:
arr[i] > arr[i + 1]
This is the first position where the array stops being non decreasing from right to left. If no such index exists, then the array is already the smallest permutation, so we return it unchanged.
2. Once the pivot index i is found, search to the right of i for the best element to swap with.
We need the largest value smaller than arr[i].
3. While searching, handle duplicates carefully.
Suppose several elements have the same candidate value. We should choose the leftmost occurrence of that value.
This maximizes the resulting permutation. 4. Swap the two elements.
After the swap, the array immediately becomes the lexicographically largest smaller permutation achievable with one swap. 5. Return the modified array.
Why it works
Lexicographical order depends most heavily on earlier positions. To get the largest permutation smaller than the original:
- We delay changes as far right as possible
- At that position, we reduce the value by the smallest possible amount
The first decreasing position from the right is exactly where the optimal change must happen. Swapping with the largest smaller value ensures the decrease is minimal. Choosing the leftmost duplicate preserves larger values earlier in the suffix, maximizing the result.
Python Solution
from typing import List
class Solution:
def prevPermOpt1(self, arr: List[int]) -> List[int]:
n = len(arr)
# Step 1: Find the first decreasing position from the right
i = n - 2
while i >= 0 and arr[i] <= arr[i + 1]:
i -= 1
# Already the smallest permutation
if i < 0:
return arr
# Step 2: Find the largest element smaller than arr[i]
j = n - 1
while arr[j] >= arr[i]:
j -= 1
# Step 3: Handle duplicates
while j > 0 and arr[j] == arr[j - 1]:
j -= 1
# Step 4: Swap
arr[i], arr[j] = arr[j], arr[i]
return arr
The implementation follows the greedy strategy directly.
First, we scan from right to left to locate the pivot index i. This is the first place where the array can be reduced lexicographically.
If no pivot exists, the array is already sorted in non decreasing order, meaning it is already the smallest possible permutation.
Next, we search from the end of the array to find the largest value smaller than arr[i]. Starting from the end ensures we encounter the largest valid candidate first.
The duplicate handling loop is crucial. If multiple equal candidates exist, we move leftward to the first occurrence of that duplicate block. This produces the lexicographically largest valid result.
Finally, we swap the pivot with the selected candidate and return the array.
Go Solution
func prevPermOpt1(arr []int) []int {
n := len(arr)
// Step 1: Find first decreasing position from the right
i := n - 2
for i >= 0 && arr[i] <= arr[i+1] {
i--
}
// Already smallest permutation
if i < 0 {
return arr
}
// Step 2: Find largest element smaller than arr[i]
j := n - 1
for arr[j] >= arr[i] {
j--
}
// Step 3: Handle duplicates
for j > 0 && arr[j] == arr[j-1] {
j--
}
// Step 4: Swap
arr[i], arr[j] = arr[j], arr[i]
return arr
}
The Go implementation mirrors the Python solution closely.
Slices in Go are mutable, so the function modifies the input slice directly and returns it.
No special overflow handling is needed because all operations are simple comparisons and swaps on integers within the problem constraints.
Unlike Python, Go does not provide tuple unpacking internally, but Go supports simultaneous assignment for swapping values cleanly.
Worked Examples
Example 1
Input:
[3,2,1]
Step 1: Find pivot
Scan from right to left.
| Index | Comparison | Result |
|---|---|---|
| 1 | 2 > 1 | Pivot found |
So:
i = 1
arr[i] = 2
Step 2: Find swap candidate
Search from the end for the largest value smaller than 2.
| Index | Value | Valid? |
|---|---|---|
| 2 | 1 | Yes |
So:
j = 2
Step 3: Swap
Swap arr[1] and arr[2].
[3,1,2]
Output:
[3,1,2]
Example 2
Input:
[1,1,5]
Step 1: Find pivot
| Index | Comparison | Result |
|---|---|---|
| 1 | 1 <= 5 | Continue |
| 0 | 1 <= 1 | Continue |
No pivot exists.
The array is already the smallest permutation.
Output:
[1,1,5]
Example 3
Input:
[1,9,4,6,7]
Step 1: Find pivot
| Index | Comparison | Result |
|---|---|---|
| 3 | 6 <= 7 | Continue |
| 2 | 4 <= 6 | Continue |
| 1 | 9 > 4 | Pivot found |
So:
i = 1
arr[i] = 9
Step 2: Find candidate
Search from the end.
| Index | Value | Smaller than 9? |
|---|---|---|
| 4 | 7 | Yes |
So:
j = 4
Step 3: Swap
Swap 9 and 7.
[1,7,4,6,9]
Output:
[1,7,4,6,9]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | At most two linear scans through the array |
| Space | O(1) | Only a few variables are used |
The algorithm performs one pass to find the pivot and another pass to find the swap candidate. Each scan is linear, so the total runtime remains O(n).
No auxiliary data structures proportional to input size are required, so the space complexity is constant.
Test Cases
from typing import List
class Solution:
def prevPermOpt1(self, arr: List[int]) -> List[int]:
n = len(arr)
i = n - 2
while i >= 0 and arr[i] <= arr[i + 1]:
i -= 1
if i < 0:
return arr
j = n - 1
while arr[j] >= arr[i]:
j -= 1
while j > 0 and arr[j] == arr[j - 1]:
j -= 1
arr[i], arr[j] = arr[j], arr[i]
return arr
sol = Solution()
assert sol.prevPermOpt1([3,2,1]) == [3,1,2] # basic decreasing case
assert sol.prevPermOpt1([1,1,5]) == [1,1,5] # already smallest permutation
assert sol.prevPermOpt1([1,9,4,6,7]) == [1,7,4,6,9] # swap with largest smaller value
assert sol.prevPermOpt1([3,1,1,3]) == [1,3,1,3] # duplicate handling
assert sol.prevPermOpt1([1]) == [1] # single element array
assert sol.prevPermOpt1([5,4,3,2,1]) == [5,4,3,1,2] # pivot near end
assert sol.prevPermOpt1([1,2,3,4,5]) == [1,2,3,4,5] # fully increasing
assert sol.prevPermOpt1([1,3,1,3]) == [1,1,3,3] # duplicate candidate values
assert sol.prevPermOpt1([9,8,7,7,6]) == [9,8,7,6,7] # duplicates near suffix
assert sol.prevPermOpt1([2,1]) == [1,2] # smallest nontrivial case
| Test | Why |
|---|---|
[3,2,1] |
Standard decreasing example |
[1,1,5] |
Already minimal permutation |
[1,9,4,6,7] |
Typical greedy swap |
[3,1,1,3] |
Validates duplicate handling |
[1] |
Smallest possible input |
[5,4,3,2,1] |
Pivot near array end |
[1,2,3,4,5] |
No valid smaller permutation |
[1,3,1,3] |
Ensures correct duplicate selection |
[9,8,7,7,6] |
Duplicate suffix values |
[2,1] |
Minimal swap scenario |
Edge Cases
One important edge case occurs when the array is already the smallest possible permutation, such as [1,1,5] or [1,2,3,4]. In these cases, there is no index i where arr[i] > arr[i+1]. A buggy implementation might still attempt a swap or access invalid indices. The algorithm handles this by checking whether the pivot index exists. If not, it immediately returns the original array unchanged.
Another subtle edge case involves duplicate values. Consider [3,1,1,3]. If we swap the 3 with the rightmost 1, we get [3,1,1,3] -> [3,1,1,3], which is incorrect. We must swap with the leftmost occurrence among equal candidates to maximize the resulting permutation. The duplicate skipping loop ensures this behavior.
A third important edge case happens when the pivot is near the end of the array, such as [5,4,3,2,1]. Here, only the last two elements need swapping. Some implementations incorrectly continue searching for a more complicated rearrangement. This algorithm correctly identifies the rightmost pivot and performs exactly one optimal swap.
A final edge case involves arrays of length one. Since no swap is possible, the array must be returned unchanged. The implementation naturally handles this because the pivot search immediately fails.