Python, Straightforward with Explanation

  • 6

    The number only has 8 digits, so there are only 8 choose 2 = 28 available swaps. Brute force them all for an O(N^2) solution which passes.

    We will store the candidates as lists of length len(num). For each candidate swap with positions (i, j), we swap the number and record if the candidate is larger than the current answer, then swap back to restore the original number. The only detail is possibly to check that we didn't introduce a leading zero. We don't actually need to check it, because our original number doesn't have one.

    def maximumSwap(self, num):
        A = list(str(num))
        ans = A[:]
        for i in xrange(len(A)):
            for j in xrange(i+1, len(A)):
                A[i], A[j] = A[j], A[i]
                if A > ans: ans = A[:]
                A[i], A[j] = A[j], A[i]
        return int("".join(ans))

    We can also get an O(N) solution. At each digit, if there is a larger digit that occurs later, we want the swap it with the largest such digit that occurs the latest.

    def maximumSwap(self, num):
        A = map(int, str(num))
        last = {x: i for i, x in enumerate(A)}
        for i, x in enumerate(A):
            for d in xrange(9, x, -1):
                if last.get(d, None) > i:
                    A[i], A[last[d]] = A[last[d]], A[i]
                    return int("".join(map(str, A)))
        return num

  • 0

    Love the O(N) solution! The line last = {x: i for i, x in enumerate(A)} is neat, too! ;)

Log in to reply

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