O(n) Python solution

  • 0

    Iterate from the least significant digit to the most significant and keep track of the current best swap. O(n) space and time

    left_index: most significant index that contains a digit less than the digit at right_index
    right_index: rightmost index that is the current best choice to swap with left_index
    max_index: index with current max digit

    class Solution(object):
        def maximumSwap(self, num):
            :type num: int
            :rtype: int
            digits = list(str(num))
            left_index = right_index = max_index = len(digits) - 1
            for i in xrange(len(digits)-2, -1, -1):
                c = digits[i]
                if c < digits[max_index]:
                    left_index, right_index = i, max_index
                elif c > digits[max_index]:
                    max_index = i
            digits[left_index], digits[right_index] = digits[right_index], digits[left_index]
            return int(''.join(digits))

Log in to reply

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