Simple Python O(nlog(n)) solution


  • 0
    M
        def maximumSwap(self, num):
            """
            :type num: int
            :rtype: int
            """
            from collections import defaultdict
            
            nums = map(int, str(num))
            sorted_nums = sorted(nums, reverse=True)
            
            indices = defaultdict(list)
            for i, num in enumerate(nums):
                indices[num].append(i)
            
            for i, num in enumerate(nums):
                if sorted_nums[i] > num:
                    # get last occurence of big
                    j = indices[sorted_nums[i]][-1]
                    
                    # swap small with big
                    tmp = nums[i]
                    nums[i] = nums[j]
                    nums[j] = tmp
                    
                    break
            
            return int(''.join(map(str, nums)))
    

Log in to reply
 

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