Sponsored
Sponsored
The idea is to always try and bring the largest possible digit to the leftmost position if it maximizes the number. For this, we can use a map to record the last occurrence of each digit. By iterating through the number, we can then attempt swapping if any larger digit occurs later.
Time Complexity: O(n), where n is the number of digits in num.
Space Complexity: O(1) as the storage is constant due to limited digit size.
1class Solution:
2 def maximumSwap(self, num: int) -> int:
3 digits = list(str(num))
4 last = {int(x): i for i, x in enumerate(digits)}
5
6 for i, x in enumerate(digits):
7 for d in range(9, int(x), -1):
8 if last.get(d, 0) > i:
9 digits[i], digits[last[d]] = digits[last[d]], digits[i]
10 return int(''.join(digits))
11 return num
12
13sol = Solution()
14num = 2736
15print(sol.maximumSwap(num))Python's dictionary comprehension allows us to easily map digits to their last occurrence. The solution involves iterating over the digits and applying a swapping strategy to achieve the largest number.