670. Maximum Swap

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

Approach 01:

class Solution {
public:
    int maximumSwap(int num) {
        string numString = to_string(num);
        vector<int> lastDigitIndex(10, -1);  // {digit: last index}

        // Record the last occurrence of each digit
        for (int i = 0; i < numString.length(); ++i)
            lastDigitIndex[numString[i] - '0'] = i;

        // Find the first opportunity to swap for maximum value
        for (int i = 0; i < numString.length(); ++i) {
            for (int d = 9; d > numString[i] - '0'; --d) {
                if (lastDigitIndex[d] > i) {
                    swap(numString[i], numString[lastDigitIndex[d]]);
                    return stoi(numString);
                }
            }
        }

        return num;  // Return the original number if no swap occurs
    }
};

class Solution:
    def maximumSwap(self, num: int) -> int:
        numString = list(str(num))
        lastDigitIndex = [-1] * 10  # {digit: last index}

        # Record the last occurrence of each digit
        for i in range(len(numString)):
            lastDigitIndex[int(numString[i])] = i

        # Find the first opportunity to swap for maximum value
        for i in range(len(numString)):
            for d in range(9, int(numString[i]), -1):
                if lastDigitIndex[d] > i:
                    numString[i], numString[lastDigitIndex[d]] = numString[lastDigitIndex[d]], numString[i]
                    return int(''.join(numString))

        return num  # Return the original number if no swap occurs

Time Complexity

• Conversion to String:

  Converting the integer num to a string using to_string() takes \(O(d)\), where \(d\) is the number of digits in the integer.

• Recording Last Occurrence:

  The loop that records the last occurrence of each digit in the number string runs once for each digit, which is \(O(d)\).

• Finding Swap Opportunity:

  The nested loop compares each digit with higher digits (9 down to the current digit). In the worst case, this would involve up to 9 comparisons for each digit, making this part of the algorithm \(O(9 \cdot d) = O(d)\).

• Overall Time Complexity:

  Since the entire algorithm operates within \(O(d)\), where \(d\) is the number of digits in the number, the overall time complexity is \(O(d)\).

Space Complexity

• String and Auxiliary Data Structures:

  We use a string representation of the number, which takes \(O(d)\) space, and a vector lastDigitIndex of size 10 to store the last occurrence of each digit, which is \(O(1)\).

• Swap Operation:

  The swap operation is done in place, and the space used for the final integer conversion using stoi() is constant.

• Overall Space Complexity:

  The overall space complexity is \(O(d)\), where \(d\) is the number of digits in the integer.