Leetcode Daily Question 17/10/2024 - 670. Maximum Swap

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.

class Solution:
  def maximumSwap(self, num: int) -> int:
    num_list = list(str(num))
    last_occurrence = {int(num): i for i, num in enumerate(num_list)}
    for i in range(len(num_list)):
      for j in range(9, int(num_list[i]), -1):
        if last_occurrence.get(j, -1) > i:
          num_list[i], num_list[last_occurrence[j]] = num_list[last_occurrence[j]], num_list[i]
          return int("".join(num_list))
    
    return num

Explanation:

The idea of this problem is to swap the leftmost smaller digit and the rightmost largest digit that comes after it in the number.

For example:
1818 -> 8811
2793 -> 7293
9973 - > 9973
1993 -> 9913

To do this, we first find the last occurrence of each unique digit in the number.

We then iterate from the least significant digit to the least. For each digit, we reverse iterate from the digit 9 down to the current digit value.

We check if this new digit value exists in the number and if the last occurrence of the new digit value exists after the current digit value.

If so, then we have found a valid swap and we exit the loop to prevent further swaps.

num_list = list(str(num)) # Make iterations easier.
last_occurrence = {int(num): i for i, num in enumerate(num_list)}

for i in range(len(num_list)): 
  for j in range(9, int(num_list[i]), -1): # We can only swap with something larger on the right not smaller.
    if last_occurrence.get(j, -1) > i: # Use .get() to catch KeyError.
      num_list[i], num_list[last_occurrence[j]] = num_list[last_occurrence[j]], num_list[i] # Swap.
      return int("".join(num_list))

return num # Return original num if not valid swap is found.

The time complexity is O(n), where n is the number of digits in num. This is because we iterate the string to create the stringified list and last_occurrence dictionary.

The space complexity is O(n). This is because we store the n digits of num in a list.

The full solution can be found near the top of the page.