O(n) time O(1) solution in one for loop


  • 0
    B

    The logic is pretty straightforward. Keep track of the max and it's temp index while traversing from c.Length - 1 to 0. Once you find a number smaller than the max record it's index and move the max temp index to maxindex which will be used to swap numbers later.

    public int MaximumSwap(int num) {
            char[] c = num.ToString().ToCharArray();
            char tempmax = char.MinValue; 
            int maxindex = -1, t = -1; // t is the temporary max index
            char min = char.MaxValue; 
            int ind = -1;
            for(int i = c.Length - 1; i >= 0; i--) {
                if(c[i] < tempmax) { // we found a number we could swap
                    min = c[i];
                    ind = i;
                    maxindex = t; // move the tempmax index to maxindex
                }
                else if(c[i] > tempmax) {
                    tempmax = c[i];
                    t = i;
                }
            }
            if(maxindex != -1 && ind != -1) {
                c[mindex] ^= c[ind];
                c[ind] ^= c[maxindex];
                c[maxindex] ^= c[ind];
            }
            return int.Parse(new string(c));
        }
    

Log in to reply
 

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