Compact O(n) time and O(1) space C++ solution with steps and examples


  • 0
    S

    Algorithm

    • Find the first local minima (or an inflexion point) left-to-right
    • If no local minima found, return the number unmodified
      • Otherwise, a swap is certain; swapping the local minima and its right neighbor will definitely give a larger number
    • But can we do better?
      • Find the max in the rest of the range, i.e. to the right of the local minima
      • Swapping the local minima and the max will definitely give another larger number
    • But can we do even better?
      • Go back leftwards starting from the local minima finding the max value smaller than the max found above
    • Swap away!

    Code

        // Time  : O(n), at most 2 passes
        // Space : O(1)
        int maximumSwap(int num)
        {
            auto str = to_string(num);
    
            // Find the first local minima (or an inflexion point) left-to-right
            int n = str.size(), li = 0;
            for ( ; li < n - 1 && str[li] >= str[li + 1]; ++li);
    
            // If no local minima found, return the number unmodified
            if (li == n)
                return num;
    
            // Otherwise, a swap is certain; swapping the values in indices li and (li + 1)
            // will definitely give a larger number
    
            // But can we do better?
    
            // Find the max in the rest of the range, i.e. to the right of li
            int maxi = n - 1;
            for (int ri = maxi - 1; ri > li; --ri)
                if (str[ri] > str[maxi])
                    maxi = ri;
    
            // Swapping the values in indices li and maxi will definitely give another
            // larger number
    
            // But can we do even better?
    
            // Go back leftwards starting from li finding the max value smaller than the
            // max found above
            for ( ; li > 0 && str[li - 1] < str[maxi]; --li);
    
            swap(str[li], str[maxi]);
    
            return stoi(str);
        }
    

    Examples

    • 93458
      • local minima is 3; max to the right of it is 8; no larger value to the left of 3 is smaller than the max, 8
      • swap 3 and 8 to get 98453
    • 76489
      • local minima is 4; max to the right of it is 9; max value to the left of the local minima, 4, smaller than the max value, 9, is 7
      • swap 7 and 9 to get 96487
    • 2649
      • local minima is 2; max to the right of it is 9
      • swap 2 and 9 to get 9642
    • 88888829
      • local minima is 2; max to the right of it is 9; max value to the left of the local minima, 2, smaller than the max value, 9, is the leftmost 8
      • swap the leftmost 8 and 9 to get 988888828

Log in to reply
 

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