O(n) 1 Pass!


  • 0

    I'm super excited! It's just so rare I can come up with something better than the top-voted solutions. :(

    int maximumSwap(int num) {
        std::string str = std::to_string(num);
        int maxFromRight = 0;
        int maxFromRightIndex = -1;
        int matchingMaxIndex = -1;
        int smallIndex = -1;
        for (int i = str.length() - 1; i >= 0; --i) {
            if (str[i] - '0' > maxFromRight) { // do not use <=
                maxFromRight = str[i] - '0';
                maxFromRightIndex = i;
            }
            if (str[i] - '0' < maxFromRight) {
                smallIndex = i;
                matchingMaxIndex = maxFromRightIndex;
            }
        }
        if (smallIndex >= 0) {
            std::swap(str[smallIndex], str[matchingMaxIndex]);
        }
        return stoi(str);
    }
    

Log in to reply
 

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