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

• #### 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

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