Maximum Swap — Greedy Last-Occurrence Digit Tracking [LC 670]

Problem Statement#

Given a non-negative integer num, you can swap two digits at most once to get the maximum valued number. Return the maximum value you can get.

Constraints:

• 0 <= num <= 10^8

Input:  num = 2736
Output: 7236

Input:  num = 9973
Output: 9973

Why This Problem Matters#

LeetCode 670 is a Meta/Facebook favorite and appears at Amazon. It tests the classic greedy digit manipulation skill: converting a number to a digit array, applying a greedy rule, and converting back. The problem forces you to think about "which swap gives the maximum gain?" — scanning from left to right for positions where a larger digit exists later in the number.

The pattern generalizes to many digit-manipulation problems: Next Permutation (LC 31), Largest Number (LC 179), and Remove K Digits (LC 402) all involve similar left-to-right greedy reasoning about digit placement.

The Core Insight#

Greedy rule: To maximize the number, swap the leftmost digit with the largest digit to its right. If there are ties (multiple occurrences of the largest), swap with the rightmost one (it displaces fewer beneficial digits).

Algorithm:

1. Convert number to digit array
2. Build last[d] = rightmost index where digit d appears
3. For each position i from left to right:
   • Check digits 9 down to digits[i] + 1
   • If any larger digit exists at some index j > i, swap digits[i] with digits[j] and return
4. If no swap was made, the number is already at maximum — return as-is

Visual Dry Run#

num = 2736, digits = [2, 7, 3, 6]

last: 2→0, 7→1, 3→2, 6→3

After swap: [7, 2, 3, 6] → result = 7236

num = 9973, digits = [9, 9, 7, 3]

last: 9→1, 7→2, 3→3

No valid swap found, return 9973.

Solution (Optimal)#

class Solution:
    def maximumSwap(self, num):
        digits = list(str(num))
        last = {int(d): i for i, d in enumerate(digits)}  # last occurrence of each digit
        for i, d in enumerate(digits):
            for x in range(9, int(d), -1):  # try largest possible digit first
                if last.get(x, -1) > i:     # larger digit exists to the right
                    j = last[x]
                    digits[i], digits[j] = digits[j], digits[i]
                    return int(''.join(digits))
        return num

var maximumSwap = function(num) {
    const digits = String(num).split('');
    const last = {};
    for (let i = 0; i < digits.length; i++) last[digits[i]] = i;
    for (let i = 0; i < digits.length; i++) {
        for (let x = 9; x > Number(digits[i]); x--) {
            if ((last[x] ?? -1) > i) {
                const j = last[x];
                [digits[i], digits[j]] = [digits[j], digits[i]];
                return Number(digits.join(''));
            }
        }
    }
    return num;
};

Time: O(n) — at most 10 inner iterations per digit position Space: O(n) — digit array and last-occurrence map

Common Mistakes#

• Swapping the first larger digit found instead of the largest — should try 9 down to d+1 to maximize the gain
• Not using the rightmost occurrence of the largest digit — using leftmost may miss a case where a digit appears multiple times
• Modifying the number in-place during the search instead of using a digit array — leads to index confusion
• Forgetting to return early after the first valid swap — only one swap is allowed
• Returning the digit array instead of converting back to integer — remember to join and convert

Interview Tips#

• Start by converting to digit array: "since at most 9 digits, this is effectively O(1)"
• Explain the greedy: "scan left to right, try to put the largest available digit in the highest-value position"
• Clarify "rightmost occurrence": if 9 appears at positions 3 and 7, swap with position 7 to keep position 3's 9 intact
• Trace through 2736 vs 9973 to show both the swap and no-swap cases
• Mention this is O(n) in digit count — for integers up to 10^8, at most 9 digits, so effectively O(1)

Follow-up Questions#

• What if you could make at most k swaps? (Greedy becomes: k passes of "put the largest available digit in the leftmost position")
• What if the number can have leading zeros? (Swap logic stays the same but output must handle leading zeros carefully)
• How does this relate to Next Permutation (LC 31)? (Both scan from right to find the pivot; both swap with the best available digit to the right)
• What if you want the minimum value instead of maximum? (Scan from left, try smallest digit 0..d-1, swap with leftmost occurrence to the right)
• Can you solve this with a single pass instead of the last-occurrence map? (Harder — the map approach is the cleanest)

Key Takeaways#

• LeetCode 670 is asked at Meta and Amazon — classic greedy digit manipulation
• Build a last-occurrence map for digits 0-9 before scanning from left to right
• For each position, try digits 9 down to d+1; swap with the rightmost occurrence of the largest available digit to the right
• Using the rightmost occurrence when there are ties ensures the best swap — leftmost occurrence would leave value on the table
• Time O(n) in digit count, effectively O(1) for integers up to 10^8 (at most 9 digits); Space O(n)
• Only one swap is allowed — return immediately after the first valid swap is found
• The pattern — scan left to right, try to maximize digit at current position — recurs in Remove K Digits, Largest Number, and Next Permutation