LC 0670 [M] Maximum Swap - ALawliet/algorithms GitHub Wiki

Backwards, find the max, if the current value less than max, it will be our candidate. If the current value bigger than max, we update max. If the current val equals to max, do nothing, because switch a number to the last occurance of max will maximize the results, since that number is less than max. If later another number less than max, we update our candidate, because switch at the front will give bigger result. Done!

class Solution:
    def maximumSwap(self, num):
        """
        :type num: int
        :rtype: int
        """
        num = [int(x) for x in str(num)]
        max_index_so_far = len(num) - 1
        a = b = 0
        
        for r in range(len(num) - 1, -1, -1):
            if num[r] > num[max_index_so_far]: # find rightmost max
                max_index_so_far = r
            else: # elif num[r] < num[max_index_so_far]: # else update swaps
                a = r
                b = max_index_so_far
            # == there is no point in updating to swap
                
        # now we have the rightmost max, and the leftmost smaller than it 
        num[a], num[b] = num[b], num[a] # swap once
        
        return int(''.join([str(x) for x in num]))

Approach #2: Greedy [Accepted] Intuition

At each digit of the input number in order, if there is a larger digit that occurs later, we know that the best swap must occur with the digit we are currently considering.

Algorithm

We will compute last[d] = i, the index i of the last occurrence of digit d (if it exists).

Afterwards, when scanning the number from left to right, if there is a larger digit in the future, we will swap it with the largest such digit; if there are multiple such digits, we will swap it with the one that occurs the latest.

class Solution(object):
    def maximumSwap(self, num):
        A = list(map(int, str(num)))
        digit_to_lastindex = {x: i for i, x in enumerate(A)}
        for i, x in enumerate(A):
            for digit in range(9, x, -1): # digits greater than x up to 9
                if digit_to_lastindex.get(digit, -1) > i:
                    A[i], A[digit_to_lastindex[digit]] = A[digit_to_lastindex[digit]], A[i]
                    return int(''.join(map(str, A)))
        return num

The greedy solution is to swap the leftmost digit with a larger digit to the right of it. For example, in 2237, 2 is swapped with 7, the largest digit to its right.

However, what if there are multiple larger digits that are the same to the right? You should always swap with the rightmost one. For example, 89999 should become 99998, not 98999. Thus, we find the rightmost max.

class Solution:
    def maximumSwap(self, num: int) -> int:
        num = [int(i) for i in str(num)]
        for i in range(len(num)-1):
            m = max(num[i+1:])
            if num[i] < m:
                for j in range(len(num)-1, i, -1):
                    if num[j] == m:
                        break
                num[i], num[j] = num[j], num[i]
                break
        return int("".join([str(i) for i in num]))