Maximum Swap

Description

Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.

Example 1:

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

Example 2:

Input: 9973
Output: 9973
Explanation: No swap.

Note:

1. The given number is in the range [0, $10^8$ ]

Solutions

My solution

Algorithm:

1. Let num[i] denote the $i^{th}$ digit.

2. Set i = 0.

3. While num[i] is larger than any digit after it, ++i.

4. Find the largest digit after num[i], say num[j] (if there are multiple largest digits, use the last one). Then swap num[i] and num[j].

class Solution {
public:
    int maximumSwap(int num) {
        vector<int> digits;
        map<int, vector<int>> hash;
        for(int i = 0; num; ++i){
            int digit = num % 10;
            digits.push_back(digit);
            hash[digit].push_back(i);
            num /= 10;
        }
        maximumSwap(digits, digits.size() - 1, hash);
        int val = 0;
        for(auto it = digits.rbegin(); it != digits.rend(); ++it){
            val = val * 10 + *it;
        }
        return val;
    }
    
    void maximumSwap(vector<int> &digits, int i, map<int, vector<int>> &hash){
        if(i < 0) return;
        auto it = hash.rbegin();
        if(digits[i] == it->first){
            if(it->second.size() == 1)
                hash.erase(it->first);
            else
                it->second.pop_back();
            maximumSwap(digits, i - 1, hash);
        }
        else{
            digits[it->second.front()] = digits[i];
            digits[i] = it->first;
        }
    }
};

A better solution

Same idea, but better implementation. The key is to store only the last occurrence of $i, \forall i \in [0, 9]$.

Credit: Java simple solution, O(n) time

class Solution {
public:
    int maximumSwap(int num) {
        string digits = to_string(num);
        vector<int> hash(10); // hash[i]: the index of the last occurrence of i
        for(int i = 0; i < digits.size(); ++i){
            hash[digits[i] - '0'] = i;
        }
        for(int i = 0; i < digits.size(); ++i){
            for(int digit = '9'; digit > digits[i]; --digit){
                if(hash[digit - '0'] > i){
                    digits[hash[digit - '0']] = digits[i];
                    digits[i] = digit;
                    return stoi(digits);
                }
            }
        }
        return stoi(digits);
    }
};