Problem Statement in English

You’re given a non-negative integer num. You can swap two digits at most once to get the maximum valued number. Return the maximum valued number you can get.

Approach

We need to be greedy here. In order to get the maximum number, we need to swap the leftmost smaller digit with the rightmost larger digit. We can achieve this by iterating through the digits and finding the best candidate for swapping.

And we’re done!

Solution in Python


class Solution:
    def maximumSwap(self, num: int) -> int:
        l = list(map(int, list(str(num))))
        N = len(l)

        for i in range(N):
            best = i
            for j in range(i + 1, N):
                if l[best] <= l[j]:
                    best = j
            if l[best] != l[i]:    
                l[i], l[best] = l[best], l[i]
                return int("".join(map(str, l)))
        
        return num

Complexity

  • Time: $O(N^2)$
    Where N is the number of digits in num. We have two nested loops, each iterating over the digits.

  • Space: $O(N)$
    We create a list to store the digits of num.

Mistakes I Made

I missed the condition l[best] == l[j] in the inner loop, which caused incorrect results for certain inputs. This condition ensures that we find the rightmost maximum digit to swap with.

And we are done.