Problem Description

You are given an integer num. Your task is to find the maximum possible value you can obtain by swapping at most two digits in the number.

The key constraints are:

• You can swap two digits at most once (or not swap at all if the number is already maximum)
• The swap involves exchanging the positions of exactly two digits
• You want to maximize the resulting number

For example:

• If num = 2736, you can swap the digits 7 and 2 to get 7236, which is the maximum possible value
• If num = 9973, the number is already at its maximum, so no swap is needed and you return 9973

The algorithm works by:

1. Converting the number to a string to easily access individual digits
2. Creating an array d that tracks, for each position, the index of the largest digit to its right (including itself)
3. Finding the leftmost position where a smaller digit can be swapped with a larger digit from the right
4. Performing the swap and converting back to an integer

The greedy approach ensures we get the maximum value by:

• Swapping the leftmost smaller digit with the rightmost occurrence of the largest available digit to its right
• This maximizes the impact on the number's value since digits on the left have higher place values

Intuition

To maximize a number by swapping at most two digits, we need to think about what makes a number larger. The leftmost (most significant) digits have the greatest impact on the number's value. So ideally, we want the largest digits to appear as far left as possible.

The key insight is that we should find the first position from the left where we can place a larger digit. To do this optimally, we need to:

1. Find which larger digit to use: For any position, we want to know what's the largest digit available to its right that we could potentially swap with. But we can't just pick any large digit - we need to track where the largest digits are located.

2. Choose the best swap position: We scan from left to right to find the first position where the current digit is smaller than the maximum digit available to its right. This ensures we're making the most impactful improvement to the number's value.

3. Handle ties carefully: When multiple positions have the same maximum digit value, we prefer the rightmost one. Why? Because if we're swapping with position i, we want to move the smallest possible value from the right side to position i, minimizing what we lose from that position.

This leads us to the approach of:

• First, preprocessing the string to build an array d where d[i] stores the index of the maximum digit from position i to the end
• Then, finding the leftmost position where we can make a beneficial swap
• Finally, performing that single swap to get the maximum number

The greedy nature of choosing the leftmost position for swapping ensures we maximize the impact, as improving a more significant digit position yields a larger overall number.

Learn more about Greedy and Math patterns.

Solution Approach

The implementation follows a greedy algorithm with preprocessing to efficiently find the optimal swap:

Step 1: Convert number to string

s = list(str(num))
n = len(s)

We convert the integer to a list of characters to easily access and swap individual digits.

Step 2: Build the maximum suffix array

d = list(range(n))
for i in range(n - 2, -1, -1):
    if s[i] <= s[d[i + 1]]:
        d[i] = d[i + 1]

We create an array d where d[i] stores the index of the maximum digit from position i to the end of the string:

• Initialize d[i] = i for all positions (each position initially points to itself)
• Traverse from right to left (from n-2 to 0)
• For each position i, compare s[i] with s[d[i+1]] (the maximum digit to the right)
• If s[i] <= s[d[i+1]], update d[i] = d[i+1] (the maximum to the right is larger or equal)
• This ensures d[i] always points to the rightmost occurrence of the maximum digit from position i onwards

Step 3: Find and perform the optimal swap

for i, j in enumerate(d):
    if s[i] < s[j]:
        s[i], s[j] = s[j], s[i]
        break

We scan from left to right to find the first position where swapping would increase the number:

• For each position i, check if s[i] < s[d[i]]
• If true, swap s[i] with s[d[i]] and break (we only need one swap)
• This ensures we swap at the leftmost beneficial position for maximum impact

Step 4: Convert back to integer

return int(''.join(s))

Join the character list back into a string and convert to integer for the final result.

Time Complexity: O(n) where n is the number of digits - we make two passes through the digits.

Space Complexity: O(n) for storing the string representation and the suffix maximum array d.

Example Walkthrough

Let's walk through the algorithm with num = 2736:

Step 1: Convert to string

• s = ['2', '7', '3', '6']
• n = 4

Step 2: Build the maximum suffix array d

Initialize d = [0, 1, 2, 3] (each position points to itself)

Now traverse from right to left:

• i = 2: Compare s[2]='3' with s[d[3]]='6'

  • Since '3' < '6', update d[2] = 3
  • d = [0, 1, 3, 3]

• i = 1: Compare s[1]='7' with s[d[2]]=s[3]='6'

  • Since '7' > '6', keep d[1] = 1
  • d = [0, 1, 3, 3]

• i = 0: Compare s[0]='2' with s[d[1]]=s[1]='7'

  • Since '2' < '7', update d[0] = 1
  • d = [1, 1, 3, 3]

The array d now shows:

• d[0] = 1: From position 0 onwards, the max digit '7' is at index 1
• d[1] = 1: From position 1 onwards, the max digit '7' is at index 1
• d[2] = 3: From position 2 onwards, the max digit '6' is at index 3
• d[3] = 3: From position 3 onwards, the max digit '6' is at index 3

Step 3: Find and perform the optimal swap

Scan from left to right:

• i = 0: Check if s[0]='2' < s[d[0]]=s[1]='7'
  • Yes! '2' < '7', so swap positions 0 and 1
  • s = ['7', '2', '3', '6']
  • Break (we're done)

Step 4: Convert back to integer

• Join: '7236'
• Convert: 7236

The algorithm correctly identifies that swapping the leftmost digit '2' with the largest available digit '7' gives us the maximum possible value of 7236.

Solution Implementation

Time and Space Complexity

The time complexity is O(log M), where M is the value of the input number num. This is because:

• Converting the number to a string takes O(log M) time (the number of digits in num is proportional to log M)
• The first loop iterates through all digits from right to left, which is O(n) where n is the number of digits, and n = O(log M)
• The second loop also iterates through the digits at most once, which is O(n) = O(log M)
• Converting back to an integer takes O(log M) time

The space complexity is O(log M) because:

• The string representation s stores all digits of the number, requiring O(log M) space
• The auxiliary array d also stores indices for each digit position, requiring O(log M) space
• The total space used is proportional to the number of digits in num, which is O(log M)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Not Finding the Rightmost Occurrence of Maximum Digit

Issue: A common mistake is swapping with the first occurrence of the maximum digit to the right, rather than the rightmost occurrence. This can lead to suboptimal results.

Example: For num = 1993, if we swap position 0 ('1') with the first '9' at position 1, we get 9193. However, swapping with the rightmost '9' at position 2 gives us 9913, which is larger.

Why it happens: When building the suffix maximum array, using < instead of <= in the comparison will point to the first occurrence rather than the last.

# Incorrect - points to first occurrence of max
for i in range(n - 2, -1, -1):
    if s[i] < s[d[i + 1]]:  # Wrong comparison
        d[i] = d[i + 1]

# Correct - points to rightmost occurrence of max
for i in range(n - 2, -1, -1):
    if s[i] <= s[d[i + 1]]:  # Correct comparison
        d[i] = d[i + 1]

Pitfall 2: Swapping Multiple Times

Issue: Performing multiple swaps instead of at most one swap, which violates the problem constraint.

Example: For num = 2736, after swapping to get 7236, continuing to look for more swaps would be incorrect.

Solution: Use break immediately after the first swap:

for i, j in enumerate(d):
    if s[i] < s[j]:
        s[i], s[j] = s[j], s[i]
        break  # Critical - stop after first swap

Pitfall 3: Incorrect Handling of Already-Maximum Numbers

Issue: Attempting to force a swap when the number is already at its maximum value.

Example: For num = 9973, the number is already optimal, but incorrect logic might try to swap equal digits.

Why it works correctly: The condition s[i] < s[j] ensures we only swap when there's an actual improvement. If the number is already maximum, this condition will never be true, and no swap occurs.

Pitfall 4: String Concatenation Instead of List Manipulation

Issue: Using string concatenation for swapping, which is inefficient and error-prone in Python since strings are immutable.

# Inefficient and error-prone
s = str(num)
s = s[:i] + s[j] + s[i+1:j] + s[i] + s[j+1:]  # Complex and bug-prone

# Better approach - use list
s = list(str(num))
s[i], s[j] = s[j], s[i]  # Simple and clear

Pitfall 5: Not Considering Single-Digit Numbers

Issue: Edge case handling for single-digit numbers like num = 7.

Solution: The algorithm naturally handles this case since:

• A single-digit number has n = 1
• The loop for i in range(n - 2, -1, -1) doesn't execute (range is empty)
• The suffix array remains d = [0]
• The swap condition s[0] < s[0] is false, so no swap occurs
• The number is returned unchanged, which is correct