LC 1053 [M] Previous Permutation With One Swap - ALawliet/algorithms GitHub Wiki

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        '''
        (1) Go from right side to left until numbers are getting smaller.
        (2) Go from left side to right until the number is both higher than previous and smaller than the number on the leftmost side.
        (3) Swap leftmost with the one from (2) and return.
        '''
        l = len(A) - 1 
        while l-1 > 0 and A[l-1] <= A[l]:
            l -= 1

        if l == 0: return A

        r = l # leftmost
        for i in range(l,len(A)):
            if A[l-1] > A[i] > A[r]:
                r = i

        A[l-1], A[r] = A[r], A[l-1]

        return A