3ms C++ code with explanation O(n) time O(1) space


  • 0
    Y
    1. to find the max, we need to swap most significant digit with as large as possible digit in lower significant position
    2. here I use a vector<int> map of length 10 to store the last appearing position of digit 0 to 9 in separately (here, not appearing digit index as 0)
      e.g. for 99732, map shoulde be {0, 0, 4, 3, 0, 0, 0, 2, 0, 1}
    3. by checking the map, we can find the largest digit in lower significant digit position
    4. complexity: time: worst case O(n) + 10*O(n), is O(n), space: 10, is O(1)
    class Solution {
    public:
        int maximumSwap(int num) {
            //change the 'int' to 'string' to deal with it one digit by one digit
            string str = std::to_string(num);
            //map store the last appearing index of number 0-9 in str
            vector<int>map(10);
            //go through to store the position
            for(int i = 0; i < str.size(); i++){
                map[str[i] - '0'] = i;
            }
            
            //from most significant position 0 to lowest significant position str.size() - 1
            for(int i = 0; i < str.size(); i++){
                //from largest digit(9) to smallest digit(0)
                for(int j = 9; j > 0 ; j--){
                    //if the digit in 'i' larger than j, 
                    //means this digit in 'i' is the largest possible one
                    //so not swap, than i++, to check next significant position
                    if(str[i] - '0' >= j) break;
                    //if find digit larger than digit in 'i', swap it and return
                    if(str[i] - '0' < j && i < map[j]){
                        swap(str[i], str[map[j]]);
                        return std::stoi(str);
                    }
                }           
            }
            //if no swap, return num
            return num;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.