Maximum Swap

You get one swap. Just one. Move two digits and make the number as big as you can. It sounds easy. But the trick is knowing which two digits to swap. The interviewer wants to see if you can find the best swap fast, not just try them all.

🎯 The Problem

You get a number and you want to make it as large as you can. Here are the rules.

• You may swap two digits at most once.
• You may also choose to swap nothing.
• Return the largest number you can make.

Say the number is 2736. The best move is to swap the 2 and the 7. That gives 7236. No other single swap makes it bigger. The biggest digit you can pull forward is the key idea. We call it the best digit to bring to the front.

Input:  num = 2736
Output: 7236

Explanation: swap the 2 and the 7 to get 7236, the largest possible.

If the number is already the biggest, like 9973, you swap nothing and return it as is.

Here are the digits laid out. We look for a bigger digit later that can move up to an early spot.

🐢 Approach 1: Try Every Swap (Brute Force)

The idea in one line: try every pair of digit positions and keep the biggest result.

The idea:

• Pick a first position.
• Pick a second position.
• Swap them and read the new number.
• Keep the biggest number you ever see.

How it works:

• Loop over every first position.
• For each, loop over every second position.
• Swap, compare with the best so far, then undo.
• After all pairs, return the biggest.

Why it is weak:

• For a number with d digits there are about d times d pairs.
• That is O(d²) work.
• Fine for short numbers, but it does far more work than needed.

Here is the brute-force code for that idea:

def maximum_swap(num):
    digits = list(str(num))
    best = num

    for i in range(len(digits)):
        for j in range(i + 1, len(digits)):
            copy = digits[:]
            copy[i], copy[j] = copy[j], copy[i]
            best = max(best, int("".join(copy)))

    return best


print(maximum_swap(2736))

⚡ Approach 2: Last Occurrence Greedy (Best)

The idea in one line: pull the largest later digit into the earliest spot, and swap its rightmost copy.

The idea:

• A bigger digit in an early spot always makes the number larger.
• So scan from the left and look for a bigger digit sitting to the right.
• Bring that bigger digit forward with one swap.

The catch about duplicates:

• The same big digit can appear more than once on the right.
• Swap its last occurrence, the rightmost copy.
• That keeps the bigger value in the important early spot and pushes the smaller digit far right.

How it works:

• Record the last position of each digit 0 to 9.
• Scan the digits from the left.
• At each spot, check digits 9 down to one above the current digit.
• The first bigger digit whose last position is to the right wins. Swap and stop.

Why it is fast:

• One setup pass, then one left-to-right scan.
• Each digit is looked at once. So it runs in O(d) time.

Here is the dry run on 2736. We find the best digit to pull forward.

Steps to Solve

1. Turn the number into a list of digits.
2. Record the last position where each digit 0 to 9 appears.
3. Scan the digits from left to right.
4. At each position, check digits 9 down to current plus one. If a bigger digit appears later, swap with its last position and stop.
5. Turn the digit list back into a number and return it.

#include <stdio.h>
#include <string.h>

int maximumSwap(int num) {
    char digits[12];
    sprintf(digits, "%d", num);   // turn number into digits
    int len = strlen(digits);

    int last[10];
    for (int d = 0; d < 10; d++) last[d] = -1;
    for (int i = 0; i < len; i++) {
        last[digits[i] - '0'] = i;   // last spot of each digit
    }

    for (int i = 0; i < len; i++) {
        for (int d = 9; d > digits[i] - '0'; d--) {
            if (last[d] > i) {        // bigger digit sits later
                char tmp = digits[i];
                digits[i] = digits[last[d]];
                digits[last[d]] = tmp;   // do the one swap
                return atoi(digits);
            }
        }
    }
    return num;  // already the largest
}

int main(void) {
    printf("%d\n", maximumSwap(2736));
    return 0;
}

7236

#include <iostream>
#include <string>
using namespace std;

int maximumSwap(int num) {
    string digits = to_string(num);  // turn number into digits
    int last[10];
    for (int d = 0; d < 10; d++) last[d] = -1;
    for (int i = 0; i < (int)digits.size(); i++) {
        last[digits[i] - '0'] = i;   // last spot of each digit
    }

    for (int i = 0; i < (int)digits.size(); i++) {
        for (int d = 9; d > digits[i] - '0'; d--) {
            if (last[d] > i) {        // bigger digit sits later
                swap(digits[i], digits[last[d]]);  // one swap
                return stoi(digits);
            }
        }
    }
    return num;  // already the largest
}

int main() {
    cout << maximumSwap(2736) << endl;
    return 0;
}

7236

public class MaximumSwap {
    static int maximumSwap(int num) {
        char[] digits = Integer.toString(num).toCharArray();  // digits
        int[] last = new int[10];
        for (int d = 0; d < 10; d++) last[d] = -1;
        for (int i = 0; i < digits.length; i++) {
            last[digits[i] - '0'] = i;   // last spot of each digit
        }

        for (int i = 0; i < digits.length; i++) {
            for (int d = 9; d > digits[i] - '0'; d--) {
                if (last[d] > i) {        // bigger digit sits later
                    char tmp = digits[i];
                    digits[i] = digits[last[d]];
                    digits[last[d]] = tmp;   // do the one swap
                    return Integer.parseInt(new String(digits));
                }
            }
        }
        return num;  // already the largest
    }

    public static void main(String[] args) {
        System.out.println(maximumSwap(2736));
    }
}

7236

def maximum_swap(num):
    digits = list(str(num))           # turn number into digits
    last = {int(d): i for i, d in enumerate(digits)}  # last spot

    for i, d in enumerate(digits):
        for big in range(9, int(d), -1):     # try bigger digits first
            if last.get(big, -1) > i:        # bigger digit sits later
                j = last[big]
                digits[i], digits[j] = digits[j], digits[i]  # one swap
                return int("".join(digits))
    return num  # already the largest


print(maximum_swap(2736))

7236

function maximumSwap(num) {
  const digits = String(num).split(""); // turn number into digits
  const last = new Array(10).fill(-1);
  for (let i = 0; i < digits.length; i++) {
    last[Number(digits[i])] = i; // last spot of each digit
  }

  for (let i = 0; i < digits.length; i++) {
    for (let big = 9; big > Number(digits[i]); big--) {
      if (last[big] > i) {
        // bigger digit sits later
        const j = last[big];
        [digits[i], digits[j]] = [digits[j], digits[i]]; // one swap
        return Number(digits.join(""));
      }
    }
  }
  return num; // already the largest
}

console.log(maximumSwap(2736));

7236

Let us walk through the Python version line by line. The line digits = list(str(num)) turns 2736 into the list ['2', '7', '3', '6']. We work on digits, not the raw number, because swapping single digits is easy on a list.

The line last = {int(d): i for i, d in enumerate(digits)} records the last position of each digit. Because we walk left to right and overwrite, the final stored index for any digit is its rightmost spot. So last[7] is 1 and last[6] is 3.

The outer loop for i, d in enumerate(digits) scans from the left. The inner loop for big in range(9, int(d), -1) tries the biggest digits first. We start at 9 and go down to just above the current digit. We want the largest possible improvement, so checking from 9 down finds it first.

The line if last.get(big, -1) > i is the heart of it. It asks if a bigger digit sits to the right of the current spot. If yes, swapping pulls that bigger digit forward. We do the swap with digits[i], digits[j] = digits[j], digits[i] and return at once. We return immediately because we only get one swap. If no swap ever helps, the number was already the largest, so we return num unchanged.

⏱️ Time and Space Complexity

The brute force tries every pair of positions, so it is O(d²) for d digits. The greedy scan records last positions once, then walks the digits one time. The inner check over 9 down is a constant, so the whole thing is O(d). We store the digits and a tiny table of ten slots, so the space is O(d).

🧩 Key Takeaways

• ✅ You get only one swap, so spend it on the biggest gain.
• ✅ Pull the largest later digit into the earliest spot you can.
• ✅ Always swap the last occurrence of that big digit, not the first.
• ✅ Record each digit’s last position once, then scan left to right.
• ✅ This turns an O(d²) search into a single O(d) pass.

🚀 What’s Next?

• Continuous Subarray Sum
• Buildings With an Ocean View