670. Maximum Swap - Detailed Explanation

Problem Statement

Description:
Given a non-negative integer num, you are allowed to swap two digits at most once to form a new number. Your task is to return the maximum number you can obtain by performing at most one swap.

Key Points:

• You can perform at most one swap.
• If no swap can improve the number, return the original number.
• The number is represented as an integer (which you might convert to a string or an array of digits for easier manipulation).

Example Inputs, Outputs, and Explanations

1. Example 1:

   • Input: num = 2736
   • Output: 7236
   • Explanation:
     • Convert to digits: [2, 7, 3, 6]
     • The optimal move is to swap the first digit (2) with the largest digit in the remainder that is greater than 2 (which is 7).
     • After the swap, the number becomes 7236, which is the maximum possible.

2. Example 2:

   • Input: num = 9973
   • Output: 9973
   • Explanation:
     • Convert to digits: [9, 9, 7, 3]
     • The number is already in its maximum form; no swap can yield a larger number.
     • Therefore, the output is 9973.

3. Example 3 (Edge Case):

   • Input: num = 0
   • Output: 0
   • Explanation:
     • The number contains only one digit (or all zeros), so no swap can change its value.

Constraints

• num is a non-negative integer.
• There is at most one swap allowed.
• The number may have multiple digits, and you need to handle numbers with varying lengths.

Hints to Approach the Solution

1. Digit Representation:

   • Convert the integer to a list or array of its digits for easy manipulation.

2. Tracking Last Occurrences:

   • Precompute and store the last (rightmost) index where each digit (0–9) occurs in the number. This helps you know where the maximum possible digit is located.

3. Greedy Strategy:

   • Traverse the digits from left to right. For each digit, check if there is a larger digit (from 9 down to one greater than the current digit) that appears later in the number. If found, swap the current digit with the rightmost occurrence of that larger digit and return the new number immediately since only one swap is allowed.

4. Optimal Swap:

   • Since you want the maximum number, perform the swap at the first instance where you can increase the number’s value, ensuring the highest-order (leftmost) digits are as large as possible.

Approach 1: Greedy Method with Last Occurrence Lookup (Optimal)

Explanation

• Preprocessing:
  Convert the number to a list of digits and record the last occurrence (index) for each digit (0–9).

• Traversal and Swap Decision:
  Iterate from the beginning of the digit list. For each digit:

  • Check for any digit from 9 down to (current_digit + 1).
  • If you find a candidate digit that occurs later (using the last occurrence lookup), swap the current digit with the rightmost occurrence of that candidate.
  • Return the new number immediately since only one swap is allowed.

• Return Original:
  If no swap can improve the number, return the original number.

Pseudocode

Convert num to a list of characters/digits: digits
Create an array/dictionary last such that for each digit d (0-9), last[d] is the last index where d appears

For i from 0 to length(digits)-1:
    For d from 9 down to (digits[i] + 1):
        If last[d] > i:
            Swap digits[i] with digits[last[d]]
            Return the integer formed by joining digits

Return num  // no swap improved the number

Approach 2: Brute Force (Not Recommended)

Explanation

• Method:
  Try every possible pair of swaps (O(n²) comparisons) and keep track of the maximum number obtained.

• Drawbacks:

  • This approach is inefficient compared to the greedy method.
  • It unnecessarily checks all possible pairs even after the best swap is identified.

Python Code