670. Maximum Swap

Problem Statement

link: LeetCode.cn LeetCode 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:

Input: num = 2736 Output: 7236

Input: num = 9973 Output: 9973

Constraints: 0 <= num <= 108

Solution Approach

The algorithm identifies the leftmost pair of digits where a swap increases the number’s value, then performs the swap to maximize the number.

Algorithm

1. Track Maximum Digits: Traverse the number from right to left, keeping track of the maximum digit encountered and its position.
2. Identify Swap Opportunity: While traversing, identify the first position where the current digit is smaller than the maximum digit found later in the sequence.
3. Perform the Swap: Swap the identified smaller digit with the maximum digit to form the largest possible number. If no swap opportunity is found, return the original number.

Implement

    class Solution:
  def maximumSwap(self, num: int) -> int:
      s = str(num)
      max_idx = len(s) - 1
      p = q = -1
      for i in range(len(s) - 2, -1, -1):
          if s[i] > s[max_idx]:
              max_idx = i
          elif s[i] < s[max_idx]:
              p, q = i, max_idx
      if p == -1:
          return num
      s = list(s)
      s[p], s[q] = s[q], s[p]
      return int(''.join(s))
  

    
    

Twitter  facebook  Email