LeetCode 1053: Previous Permutation With One Swap

Problem Restatement

We are given an array of positive integers arr.

We need to return the lexicographically largest permutation smaller than arr that can be obtained with at most one swap.

If not possible, return arr.

The official constraints state that 1 <= arr.length <= 10^4 and 1 <= arr[i] <= 10^4.

Input and Output

Function shape:

def prevPermOpt1(arr: list[int]) -> list[int]:
    ...

Examples

Example 1:

arr = [3, 2, 1]

Previous: [3, 1, 2]. One swap of index 1 and 2.

Answer:

[3, 1, 2]

Example 2:

arr = [1, 1, 5]

For arr = [1, 1, 5], the array is already in nondecreasing order. No single swap can produce a lexicographically smaller permutation, so we return the array unchanged.

Answer for [1, 1, 5]:

[1, 1, 5]

Key Insight

To get the previous permutation with one swap:

1. Find the rightmost position i where arr[i] > arr[i+1] (a descent). If none, already the smallest.
2. Find the largest arr[j] to the right of i that is less than arr[i]. Among equal values, pick the leftmost (to avoid duplicate swaps).
3. Swap arr[i] with arr[j].

Correctness

We want the largest permutation smaller than arr. The rightmost descent is the best place to make a swap (affects only the suffix). Swapping with the largest value smaller than arr[i] to its right gives the lexicographically largest decrease.

Edge Cases

• Check the minimum input size allowed by the constraints.
• Verify duplicate values or tie cases if the input can contain them.
• Keep the return value aligned with the exact failure case in the statement.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

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

Testing

def run_tests():
    s = Solution()

    assert s.prevPermOpt1([3,2,1]) == [3,1,2]
    assert s.prevPermOpt1([1,1,5]) == [1,1,5]
    assert s.prevPermOpt1([1,9,4,6,7]) == [1,7,4,6,9]
    assert s.prevPermOpt1([3,1,1,3]) == [1,3,1,3]

    print("all tests passed")

run_tests()