LC1053. Previous Permutation With One Swap

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        """ main idea: two ptr to find two elements in array, swap them.  there are several cases to consider:  (1) len of A <2;  (2) A is in ascending order => nothing to swap since it's already smallest permutation (3)when look for right value, we need to seek from right side of left ptr, the goal is to find max value(position) that is smaller than left value 
        1. edge case, A len <2
        2. right -> left, find first position that not follow ascending order  => mark left ptr  
        3. check if left ptr is out of boundry and we havent found abnormal val, mean current permutation is smallest. otherwise step4 
        4. start from left ptr -> the end, get the position of max value(smaller than left value )
        5. swap left val with right val 
        
        """
        pos,max_v = None,-1
        n = len(A)
        if n < 2:
            return arr
        l = n-2 
        
        while l>=0 and A[l] <= A[l+1]:
            l -= 1 
           
        if l < 0:
            return A
        
        r = l+1
        ## find largest element at right of index which is less than A[index];
        # find the max val and max_v < A[l]
        while r < n:
            if A[r] < A[l] and A[r]> max_v:
                max_v = A[r]
                pos = r 
            r += 1
            
            # swap 
        A[l],A[pos] = A[pos], A[l]
            
        return A