Maximum Swap

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, 108]

===========

class Solution {

    

vector<int> convertToVector(int num) {

    vector<int> nums;

    while (num != 0) {

        nums.push_back(num % 10);

        num = num / 10;

    }

    reverse(nums.begin(), nums.end());

    return nums;

}

    

int convertToNum(vector<int> nums) {

    int num = 0;

    for (auto & number : nums) {

        num *= 10;

        num += number;

    }

    return num;

}

    

public:

    int maximumSwap(int num) {

        if (num == 0) {

            return 0;

        }

        vector<int> nums = convertToVector(num);

        unordered_map<int, int> mp;

        

        for (int i = 0; i < nums.size(); i++) {

            mp[nums[i]] = i;

        }

        

        bool found = false;

        for (int i = 0; i < nums.size(); i++) {

            int cur_num = nums[i];

            for (int bigger_num = 9; bigger_num > cur_num; bigger_num--) {

                if (mp.count(bigger_num) != 0 && mp[bigger_num] > i) {

                    iter_swap(nums.begin() + i, nums.begin() + mp[bigger_num]);

                    found = true;

                    break;

                }

            }

            if (found) {

                break;

            }

        }

        

        return convertToNum(nums);

    }

};

========== Better one =======

class Solution { public: int maximumSwap(int num) { string s = to_string(num); for(int i=9;i>=1;i--){ char c = i+'0'; int pos1=-1; int pos2=-1; for(int j=s.size()-1;j>=0;j--){ if(s[j]==c){ pos1 = j; break; } } for(int j=0;j<s.size();j++){ if(s[j]<c){ pos2 = j; break; } } if(pos1!=-1 && pos2!=-1){ if(pos2<pos1){ swap(s[pos1],s[pos2]); break; } } } return stoi(s); } };

===========

Approach #2: Greedy [Accepted]

Intuition

At each digit of the input number in order, if there is a larger digit that occurs later, we know that the best swap must occur with the digit we are currently considering.

Algorithm

We will compute $\text{last[d] = i}$, the index $\text{i}$ of the last occurrence of digit $\text{d}$ (if it exists).

Afterwards, when scanning the number from left to right, if there is a larger digit in the future, we will swap it with the largest such digit; if there are multiple such digits, we will swap it with the one that occurs the latest.

Complexity Analysis

• Time Complexity: $O(N)$, where $N$ is the total number of digits in the input number. Every digit is considered at most once.
• Space Complexity: $O(1)$. The additional space used by $\text{last}$ only has up to 10 values.