Maximum Swap

Medium
357.

Maximum Swap

Maximum Swap is a medium coding problem on math and greedy, asked in Amazon, Google, Microsoft and Meta interviews.

You are given an integer num. You may swap two of its digits at most once.

Return the maximum value you can obtain.

Example 1

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

Example 2

Input
num = 9973
Output
9973
Explanation
No swap improves it.

Example 3

Input
num = 1993
Output
9913

Constraints

  • 0 <= num <= 100000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} num
 * @return {number}
 */
var maximumSwap = function(num) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Swap — Solution in Python, Java & C++

Maximum Swap solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.

Maximum Swap is a medium coding problem on math and greedy, asked in Amazon, Google, Microsoft and Meta interviews.

  • Difficulty: Medium
  • Topics: Math, Greedy
  • Asked at: Amazon, Google, Microsoft, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an integer num. You may swap two of its digits at most once.

Return the maximum value you can obtain.

Example 1

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

Example 2

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

Example 3

Input: num = 1993
Output: 9913

Constraints

  • 0 <= num <= 100000000

Hints for Maximum Swap

  1. Hint 1

    Scan from the most significant digit; the first place you can raise is where the swap belongs.

  2. Hint 2

    For that position, bring in the largest digit that appears later.

  3. Hint 3

    If that largest digit occurs several times later, take the rightmost occurrence — moving a digit from further right leaves more value behind.

How to solve Maximum Swap

Scan from the left for the first position that can be raised; swap in the largest digit that appears later, taking its rightmost occurrence.

Approach

  1. Record the last index of each digit.
  2. For each position i, for bigger from 9 down to digit + 1: if bigger occurs after i, swap with its last occurrence and return.

Why it works

Raising the most significant possible position gives the biggest gain; among candidates for that position the largest digit wins; and taking the rightmost occurrence moves the smaller digit as far right as possible.

Complexity

  • Time — O(digits)
  • Space — O(1)

Pitfalls

  • Swapping with the first occurrence of the bigger digit can be worse — 1993 → 9913, not 9193.

Reference solution

Python

def maximumSwap(num: int) -> int:
    digits = list(str(num))
    last = {int(d): i for i, d in enumerate(digits)}
    for i, d in enumerate(digits):
        for bigger in range(9, int(d), -1):
            if last.get(bigger, -1) > i:
                j = last[bigger]
                digits[i], digits[j] = digits[j], digits[i]
                return int("".join(digits))
    return num

Java

public static int maximumSwap(int num) {
    char[] digits = String.valueOf(num).toCharArray();
    int[] lastIndex = new int[10];
    for (int i = 0; i < 10; i++) lastIndex[i] = -1;
    for (int i = 0; i < digits.length; i++) lastIndex[digits[i] - '0'] = i;
    for (int i = 0; i < digits.length; i++) {
        for (int d = 9; d > digits[i] - '0'; d--) {
            if (lastIndex[d] > i) {
                int j = lastIndex[d];
                char t = digits[i];
                digits[i] = digits[j];
                digits[j] = t;
                return Integer.parseInt(new String(digits));
            }
        }
    }
    return num;
}

C++

int maximumSwap(int num) {
    string digits = to_string(num);
    vector<int> lastIndex(10, -1);
    for (int i = 0; i < (int) digits.size(); i++) lastIndex[digits[i] - '0'] = i;
    for (int i = 0; i < (int) digits.size(); i++) {
        for (int d = 9; d > digits[i] - '0'; d--) {
            if (lastIndex[d] > i) {
                int j = lastIndex[d];
                char t = digits[i];
                digits[i] = digits[j];
                digits[j] = t;
                return stoi(digits);
            }
        }
    }
    return num;
}

JavaScript

var maximumSwap = function(num) {
    const digits = String(num).split("");
    const lastIndex = new Array(10).fill(-1);
    for (let i = 0; i < digits.length; i++) lastIndex[Number(digits[i])] = i;
    for (let i = 0; i < digits.length; i++) {
        for (let d = 9; d > Number(digits[i]); d--) {
            if (lastIndex[d] > i) {
                const j = lastIndex[d];
                const t = digits[i];
                digits[i] = digits[j];
                digits[j] = t;
                return parseInt(digits.join(""), 10);
            }
        }
    }
    return num;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Greedy Algorithms