1053. Previous Permutation With One Swap

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 (A swap exchanges the positions of two numbers arr[i] and arr[j]). If it cannot be done, then return the same array.

 

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

Solution

previous-permutation-with-one-swap.py

class Solution:
    def prevPermOpt1(self, arr: List[int]) -> List[int]:
        n = len(arr)
        if n <= 1: return arr

        index = -1
        for i in range(n - 1, 0, -1):
            if arr[i] < arr[i - 1]:
                index = i - 1
                break

        if index == -1: return arr
        for i in range(n - 1, index - 1, -1):
            if arr[i] < arr[index] and arr[i] != arr[i - 1]:
                arr[i], arr[index] = arr[index], arr[i]
                break

        return arr