LeetCode 670. Maximum Swap

Description:

Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.

Note:

Example:

input:

2736

output:

7236

explanation:

Swap the number 2 and the number 7.

input:

9973

output:

9973

explanation:

No swap.

Solution:

class Solution:
    def maximumSwap(self, num):
        """
        :type num: int
        :rtype: int
        """
        numStr = repr(num)
        numDigit = [int(ch) for ch in numStr]

        if len(numDigit) <= 1:
            return num

        maxTable = [-1] * len(numDigit)

        currentMax = (-1, -1)
        for i in range(len(numDigit) - 1, -1, -1):
            if numDigit[i] > currentMax[0]:
                currentMax = (numDigit[i], i)
            maxTable[i] = currentMax

        for i in range(len(numDigit)):
            if maxTable[i][0] > numDigit[i]:
                # swap numDigit[i] and numDigit[maxTable[i][1]]
                temp = numDigit[i]
                numDigit[i] = numDigit[maxTable[i][1]]
                numDigit[maxTable[i][1]] = temp
                break

        result = 0
        for i in range(len(numDigit)):
            result += numDigit[len(numDigit) - 1 - i] * pow(10, i)

        return result

Starting backwards, keep track of a maxTable that stores the largest digit in the range [i:len(numDigit)]. Scan and compare each element in numDigit and maxTable from the right. If an element in maxTable is greater than its corresponding element in numDigit, execute the swap.