Problem description:

You are given an integer num. You can swap two digits at most once to get the maximum valued number.

Return the maximum valued number you can get.

Example 1:

1
2
3
Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2:

1
2
3
Input: num = 9973
Output: 9973
Explanation: No swap.

Constraints:

  • 0 <= num <= 108

Solution:

Use an array to note the last occurence of each digits(0~9)

Then traverse from left to right, for arr[i], if we find there’s a bigger digit and its locate after i, then we do the swap and return it.

Note we could start from 9 to int(arr[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def maximumSwap(self, num: int) -> int:
        '''
        traverse from left to right
        use an array to keep all the last index of integer(0~9)
        
        traverse from left to right again
        if could find a larger integer is located after num[i], swap them
        '''
        
        digitIdx = [-1]*10
        arr = list(str(num))
        for i in range(len(arr)):
            digitIdx[ord(arr[i])-ord('0')] = i
        # print(arr, digitIdx)
        
        for i in range(len(arr)):
            # for this number arr[i], find larger and the number after position i
            for j in range(9, int(arr[i]), -1):
                if digitIdx[j] != -1 and digitIdx[j] > i:
                    # print(arr[i], arr[digitIdx[j]])
                    arr[i], arr[digitIdx[j]] = arr[digitIdx[j]], arr[i]
                    return int(''.join(arr)) 
        return num

time complexity: $O(n)$
space complexity: $O(1)$
reference:
related problem: