670. Maximum Swap

Jump to Solution: Python Java C++ JavaScript C#

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.

Examples:

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 ≤ 10⁸

Python Solution

class Solution:
    def maximumSwap(self, num: int) -> int:
        # Convert number to list of digits
        digits = list(str(num))
        n = len(digits)
        
        # For each digit, find the largest digit that comes after it
        last = {int(x): i for i, x in enumerate(digits)}
        
        # Check each position from left to right
        for i in range(n):
            current = int(digits[i])
            # Check all possible digits larger than current
            for d in range(9, current, -1):
                # If we find a larger digit that comes after current position
                if d in last and last[d] > i:
                    # Swap the digits
                    digits[i], digits[last[d]] = digits[last[d]], digits[i]
                    return int(''.join(digits))
        
        return num

Alternative Solution:

class Solution:
    def maximumSwap(self, num: int) -> int:
        nums = list(str(num))
        max_idx = {int(x): i for i, x in enumerate(nums)}
        
        for i, x in enumerate(nums):
            for d in range(9, int(x), -1):
                if d in max_idx and max_idx[d] > i:
                    nums[i], nums[max_idx[d]] = nums[max_idx[d]], nums[i]
                    return int(''.join(nums))
        
        return num

Implementation Notes:

Time complexity: O(n) where n is number of digits
Space complexity: O(n) to store the digits
Uses dictionary to store last occurrence of each digit

Java Solution

class Solution {
    public int maximumSwap(int num) {
        char[] digits = String.valueOf(num).toCharArray();
        int[] last = new int[10];
        
        // Record last position of each digit
        for (int i = 0; i < digits.length; i++) {
            last[digits[i] - '0'] = i;
        }
        
        // Check each position from left to right
        for (int i = 0; i < digits.length; i++) {
            int currentDigit = digits[i] - '0';
            // Look for larger digits
            for (int d = 9; d > currentDigit; d--) {
                if (last[d] > i) {
                    // Swap digits
                    char temp = digits[i];
                    digits[i] = digits[last[d]];
                    digits[last[d]] = temp;
                    return Integer.parseInt(new String(digits));
                }
            }
        }
        
        return num;
    }
}

C++ Solution

class Solution {
public:
    int maximumSwap(int num) {
        string digits = to_string(num);
        vector last(10, -1);
        
        // Record last position of each digit
        for (int i = 0; i < digits.length(); i++) {
            last[digits[i] - '0'] = i;
        }
        
        // Check each position from left to right
        for (int i = 0; i < digits.length(); i++) {
            int currentDigit = digits[i] - '0';
            // Look for larger digits
            for (int d = 9; d > currentDigit; d--) {
                if (last[d] > i) {
                    // Swap digits
                    swap(digits[i], digits[last[d]]);
                    return stoi(digits);
                }
            }
        }
        
        return num;
    }
};

JavaScript Solution

/**
 * @param {number} num
 * @return {number}
 */
var maximumSwap = function(num) {
    const digits = String(num).split('');
    const last = new Array(10).fill(-1);
    
    // Record last position of each digit
    for (let i = 0; i < digits.length; i++) {
        last[digits[i]] = i;
    }
    
    // Check each position from left to right
    for (let i = 0; i < digits.length; i++) {
        const currentDigit = parseInt(digits[i]);
        // Look for larger digits
        for (let d = 9; d > currentDigit; d--) {
            if (last[d] > i) {
                // Swap digits
                [digits[i], digits[last[d]]] = [digits[last[d]], digits[i]];
                return parseInt(digits.join(''));
            }
        }
    }
    
    return num;
};

C# Solution

public class Solution {
    public int MaximumSwap(int num) {
        char[] digits = num.ToString().ToCharArray();
        int[] last = new int[10];
        
        // Record last position of each digit
        for (int i = 0; i < digits.Length; i++) {
            last[digits[i] - '0'] = i;
        }
        
        // Check each position from left to right
        for (int i = 0; i < digits.Length; i++) {
            int currentDigit = digits[i] - '0';
            // Look for larger digits
            for (int d = 9; d > currentDigit; d--) {
                if (last[d] > i) {
                    // Swap digits
                    char temp = digits[i];
                    digits[i] = digits[last[d]];
                    digits[last[d]] = temp;
                    return int.Parse(new string(digits));
                }
            }
        }
        
        return num;
    }
}

Implementation Notes:

Uses array to store last occurrence of each digit
Time complexity: O(n) where n is number of digits
Space complexity: O(1) since array size is fixed at 10
Only performs one swap to get maximum value