670. Maximum Swap

[mah-shamim]

Topics: Math, Greedy

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 1:

• Input: num = 2736
• Output: 7236
• Explanation: Swap the number 2 and the number 7.

Example 2:

• Input: num = 9973
• Output: 9973
• Explanation: No swap.

Constraints:

• 0 <= num <= 108

[kovatz]

We can follow a greedy approach. Here's a step-by-step explanation and the solution:

Approach:

1. Convert the Number to an Array: Since digits need to be swapped, converting the number into an array of digits makes it easier to access and manipulate individual digits.
2. Track the Rightmost Occurrence of Each Digit: Store the rightmost position of each digit (0-9) in an array.
3. Find the Best Swap Opportunity: Traverse through the number's digits from left to right, and for each digit, check if there is a higher digit that appears later. If so, swap them to maximize the number.
4. Perform the Swap and Break: As soon as the optimal swap is found, perform the swap and break the loop.
5. Convert the Array Back to a Number: After the swap, convert the array of digits back to a number and return it.

Let's implement this solution in PHP: 670. Maximum Swap

<?php
/**
 * @param Integer $num
 * @return Integer
 */
function maximumSwap($num) {
    // Convert the number into an array of characters (digits)
    $numStr = strval($num);
    $numArr = str_split($numStr);
    $n = count($numArr);
    
    // Array to store the last occurrence of each digit (0-9)
    $last = array_fill(0, 10, -1);
    
    // Populate the last occurrence array
    for ($i = 0; $i < $n; $i++) {
        $last[$numArr[$i]] = $i;
    }
    
    // Traverse the digits to find the best place to swap
    for ($i = 0; $i < $n; $i++) {
        // Check for a larger digit that appears later
        for ($d = 9; $d > $numArr[$i]; $d--) {
            if ($last[$d] > $i) {
                // Swap digits
                $temp = $numArr[$i];
                $numArr[$i] = $numArr[$last[$d]];
                $numArr[$last[$d]] = $temp;
                
                // Convert back to an integer and return
                return intval(implode('', $numArr));
            }
        }
    }
    
    // If no swap was made, return the original number
    return $num;
}

// Example usage:
echo maximumSwap(2736); // Output: 7236
echo maximumSwap(9973); // Output: 9973
?>

Explanation:

• Step 1: strval($num) converts the integer into a string, and str_split($numStr) splits it into an array of digits.
• Step 2: The last array keeps track of the rightmost index of each digit from 0 to 9.
• Step 3: We iterate through each digit and look for a larger digit that can be swapped.
• Step 4: If a suitable larger digit is found (that appears later in the number), the digits are swapped.
• Step 5: The modified array is converted back to a string and then to an integer using intval().

Complexity:

• Time Complexity: O(n), where n is the number of digits in num. This is because we make a pass through the number to fill the last array and another pass to find the optimal swap.
• Space Complexity: O(1) (ignoring the input size) since the last array is fixed with 10 elements.

This solution efficiently finds the maximum value by swapping digits only once, as required.

[mah-shamim]

Thanks to solve the "Maximum Swap" problem

[kovatz]

Thanks