Short O(n) Python AC Code

  • 0


    1. Find the first increasing digits in the number which separate the number into two parts.
    2. Find the maximum digit in the second part.
    3. Find the first digit in the first part which is smaller than the maximum digit in step 2 and swap them.
    class Solution:
        def maximumSwap(self, num):
            :type num: int
            :rtype: int
            nums = [i for i in str(num)]
            increasing = [i for i, v in enumerate(nums) if i > 0 and nums[i-1] < v]
            if not increasing:
                return num
            max_digit = max(nums[increasing[0]:])
            max_index = [i for i, v in enumerate(nums) if v == max_digit][-1]
            for i in range(max_index):
                if nums[i] < nums[max_index]:
                    nums[i], nums[max_index] = nums[max_index], nums[i]
            return int("".join(nums))

Log in to reply

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