Python O(n) time O(n) memory solution with comments


  • 0
    D
    def maximumSwap(self, num):
        """
        :type num: int
        :rtype: int
        """
        
        # transform to an array of integers containing the digits
        arr=[int(a) for a in str(num)]
        
        # find the decreasing run from the highest digit down
        i=1
        while i<len(arr) and arr[i]<=arr[i-1]:
            i+=1
            
        # if the end is reached, the array is sorted in decreasing order
        # meaning it is already the largest
        if i==len(arr):
            return num
        
        # find the maximum from the ith element on
        m=max(arr[i:])
        a=0
        b=0
        
        # find the last element from ith element on with value m
        for j in range(len(arr)-1,0,-1):
            if arr[j]==m:
                b=j
                break
                
        # find the first element before the ith element that has value less than m
        for j in range(i):
            if arr[j]<m:
                a=j
                break
                
        # swap them
        temp=arr[a]
        arr[a]=arr[b]
        arr[b]=temp
        
        # recast it into an integer
        return int("".join([str(ele) for ele in arr]))

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.