670. Maximum Swap

Description

You are given an integer num. You can swap two digits at most once to get the maximum valued number.

Return the maximum valued number you can get.

Example 1:

Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2:

Input: num = 9973
Output: 9973
Explanation: No swap.

Constraints:

0 <= num <= 10⁸

Solutions

Solution 1: Greedy Algorithm

Thinking

Swap at most two digits to maximize the number. Trying every pair is unnecessary.

From the right, record the index of the largest digit to the right (inclusive). From the left, swap at the first \(s[i]<s[d[i]]\). That raises the highest possible place.

First, we convert the number into a string \(s\). Then, we traverse the string \(s\) from right to left, using an array or hash table \(d\) to record the position of the maximum number to the right of each number (it can be the position of the number itself).

Next, we traverse \(d\) from left to right. If \(s[i] < s[d[i]]\), we swap them and exit the traversal process.

Finally, we convert the string \(s\) back into a number, which is the answer.

The time complexity is \(O(\log M)\), and the space complexity is \(O(\log M)\). Here, \(M\) is the range of the number \(num\).

Python3JavaC++GoTypeScriptRust

class Solution:
    def maximumSwap(self, num: int) -> int:
        s = list(str(num))
        n = len(s)
        d = list(range(n))
        for i in range(n - 2, -1, -1):
            if s[i] <= s[d[i + 1]]:
                d[i] = d[i + 1]
        for i, j in enumerate(d):
            if s[i] < s[j]:
                s[i], s[j] = s[j], s[i]
                break
        return int(''.join(s))

class Solution {
    public int maximumSwap(int num) {
        char[] s = String.valueOf(num).toCharArray();
        int n = s.length;
        int[] d = new int[n];
        for (int i = 0; i < n; ++i) {
            d[i] = i;
        }
        for (int i = n - 2; i >= 0; --i) {
            if (s[i] <= s[d[i + 1]]) {
                d[i] = d[i + 1];
            }
        }
        for (int i = 0; i < n; ++i) {
            int j = d[i];
            if (s[i] < s[j]) {
                char t = s[i];
                s[i] = s[j];
                s[j] = t;
                break;
            }
        }
        return Integer.parseInt(String.valueOf(s));
    }
}

class Solution {
public:
    int maximumSwap(int num) {
        string s = to_string(num);
        int n = s.size();
        vector<int> d(n);
        iota(d.begin(), d.end(), 0);
        for (int i = n - 2; ~i; --i) {
            if (s[i] <= s[d[i + 1]]) {
                d[i] = d[i + 1];
            }
        }
        for (int i = 0; i < n; ++i) {
            int j = d[i];
            if (s[i] < s[j]) {
                swap(s[i], s[j]);
                break;
            }
        }
        return stoi(s);
    }
};

func maximumSwap(num int) int {
    s := []byte(strconv.Itoa(num))
    n := len(s)
    d := make([]int, n)
    for i := range d {
        d[i] = i
    }
    for i := n - 2; i >= 0; i-- {
        if s[i] <= s[d[i+1]] {
            d[i] = d[i+1]
        }
    }
    for i, j := range d {
        if s[i] < s[j] {
            s[i], s[j] = s[j], s[i]
            break
        }
    }
    ans, _ := strconv.Atoi(string(s))
    return ans
}

function maximumSwap(num: number): number {
    const list = new Array();
    while (num !== 0) {
        list.push(num % 10);
        num = Math.floor(num / 10);
    }
    const n = list.length;
    const idx = new Array();
    for (let i = 0, j = 0; i < n; i++) {
        if (list[i] > list[j]) {
            j = i;
        }
        idx.push(j);
    }
    for (let i = n - 1; i >= 0; i--) {
        if (list[idx[i]] !== list[i]) {
            [list[idx[i]], list[i]] = [list[i], list[idx[i]]];
            break;
        }
    }
    let res = 0;
    for (let i = n - 1; i >= 0; i--) {
        res = res * 10 + list[i];
    }
    return res;
}

impl Solution {
    pub fn maximum_swap(mut num: i32) -> i32 {
        let mut list = {
            let mut res = Vec::new();
            while num != 0 {
                res.push(num % 10);
                num /= 10;
            }
            res
        };
        let n = list.len();
        let idx = {
            let mut i = 0;
            (0..n)
                .map(|j| {
                    if list[j] > list[i] {
                        i = j;
                    }
                    i
                })
                .collect::<Vec<usize>>()
        };
        for i in (0..n).rev() {
            if list[i] != list[idx[i]] {
                list.swap(i, idx[i]);
                break;
            }
        }
        let mut res = 0;
        for i in list.iter().rev() {
            res = res * 10 + i;
        }
        res
    }
}

Solution 2: Space Optimized Greedy

Thinking

Method 1 stores a right-max index array. One right-to-left scan can keep the best seen digit and the leftmost profitable swap, without the extra array.

TypeScriptJavaScript

function maximumSwap(num: number): number {
    const ans = [...String(num)];
    let [min, max, maybeMax, n] = [-1, -1, -1, ans.length];

    for (let i = n - 1; i >= 0; i--) {
        if (ans[i] > (ans[maybeMax] ?? -1)) maybeMax = i;
        if (i < maybeMax && ans[i] < ans[maybeMax]) {
            [min, max] = [i, maybeMax];
        }
    }

    if (~min && ~max && min < max) {
        [ans[min], ans[max]] = [ans[max], ans[min]];
    }

    return +ans.join('');
}

function maximumSwap(num) {
    const ans = [...String(num)];
    let [min, max, maybeMax, n] = [-1, -1, -1, ans.length];

    for (let i = n - 1; i >= 0; i--) {
        if (ans[i] > (ans[maybeMax] ?? -1)) maybeMax = i;
        if (i < maybeMax && ans[i] < ans[maybeMax]) {
            [min, max] = [i, maybeMax];
        }
    }

    if (~min && ~max && min < max) {
        [ans[min], ans[max]] = [ans[max], ans[min]];
    }

    return +ans.join('');
}

670. Maximum Swap

Description

Solutions

Solution 1: Greedy Algorithm

Solution 2: Space Optimized Greedy

Comments