# C++ one-pass simple & fast solution: 1-3ms, O(n) time

• Actually this problem can be easily solved by only one pass from backward. During the scan, we only need to do 2 things:

1. record the largest digit (maxdigit) and its corresponding index (maxidx);
2. if the current digit is smaller than the largest digit, this digit and the largest digit are the best candidate for max swap so far. In this case, this digit pair is recorded (leftidx and rightidx).
``````
int maximumSwap(int num) {
string numstr = std::to_string(num);

int maxidx = -1; int maxdigit = -1;
int leftidx = -1; int rightidx = -1;

for (int i = numstr.size() - 1; i >= 0; --i) {
// current digit is the largest by far
if (numstr[i] > maxdigit) {
maxdigit = numstr[i];
maxidx = i;
continue;
}

// best candidate for max swap if there is no more
// such situation on the left side
if (numstr[i] < maxdigit) {
leftidx = i;
rightidx = maxidx;
}
}

// num is already in order
if (leftidx == -1) return num;

std::swap(numstr[leftidx], numstr[rightidx]);

return std::stoi(numstr);
}
``````

• Expressive solutions!

• Really like your solution! simple and efficient :)

• I really like your solution. you did what required. only one swap!! Great job!! I translate it into python as follows.

``````    def maximumSwap(self, num):
"""
:type num: int
:rtype: int
"""
num_str = list(str(num))
max_i, max_n, left, right = -1, -1, -1, -1
for i in xrange(len(num_str)-1, -1, -1):
if int(num_str[i]) > int(max_n):
max_n = num_str[i]
max_i = i
continue

if int(num_str[i]) < int(max_n):
left = i
right = max_i

if left == -1: return num
else:
num_str[left], num_str[right] = num_str[right], num_str[left]
return int("".join(num_str))
``````

• @WeiFoo it's my pleasure :), it is great to see you like my solution and translated it to other language, thx

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