Approach: Greedy: swap first digit with the largest later digit

def maximumSwap(n):
    d = list(str(n))
    last = {int(c): i for i, c in enumerate(d)}
    for i, c in enumerate(d):
        for k in range(9, int(c), -1):
            if last.get(k, -1) > i:
                d[i], d[last[k]] = d[last[k]], d[i]
                return int(''.join(d))
    return n

Complexity: O(log n) time, O(1) space.

Full Solution — all languages

class Solution:
    def maximumSwap(self, n):
        d = list(str(n))
        last = {int(c): i for i, c in enumerate(d)}
        for i, c in enumerate(d):
            for k in range(9, int(c), -1):
                if last.get(k, -1) > i:
                    d[i], d[last[k]] = d[last[k]], d[i]
                    return int(''.join(d))
        return n

import java.util.*;
class Solution {
    public int maximumSwap(int n) {
        char[] d = Integer.toString(n).toCharArray();
        int[] last = new int[10];
        for (int i = 0; i < d.length; i++) last[d[i] - '0'] = i;
        for (int i = 0; i < d.length; i++) {
            for (int k = 9; k > d[i] - '0'; k--) {
                if (last[k] > i) {
                    char t = d[i];
                    d[i] = d[last[k]];
                    d[last[k]] = t;
                    return Integer.parseInt(new String(d));
                }
            }
        }
        return n;
    }
}

#include <bits/stdc++.h> using namespace std;
class Solution {
    public: int maximumSwap(int n) {
        string d = to_string(n);
        int last[10] = {0};
        for (int i = 0; i < (int)d.size(); i++) last[d[i] - '0'] = i;
        for (int i = 0; i < (int)d.size(); i++) {
            for (int k = 9; k > d[i] - '0'; k--) {
                if (last[k] > i) {
                    swap(d[i], d[last[k]]);
                    return stoi(d);
                }
            }
        }
        return n;
    }
};

/**
 * @param {number} n
 * @return {number}
 */ var maximumSwap = function(n) {
    const d = String(n).split('');
    const last = {};
    for (let i = 0; i < d.length; i++) last[d[i]] = i;
    for (let i = 0; i < d.length; i++) {
        for (let k = 9; k > +d[i]; k--) {
            if (last[k] !== undefined && last[k] > i) {
                const t = d[i];
                d[i] = d[last[k]];
                d[last[k]] = t;
                return parseInt(d.join(''), 10);
            }
        }
    }
    return n;
};

Maximum Swap

Example 1

Example 2

Constraints