Maximum Swap: Greedy Digit Swap

Given a non-negative integer, you are allowed to swap two digits at most once to get the maximum valued number. Return the maximum valued number. This is LeetCode 670: Maximum Swap.

A few examples:

• 2736 becomes 7236 (swap the 2 and 7)
• 9973 stays 9973 (already the largest arrangement)
• 1993 becomes 9913 (swap the 1 and the last 9)

The trick is figuring out which two digits to swap. You want to place the largest possible digit as far left as possible, and if there are ties, you want the rightmost occurrence of that digit (to keep the leftmost copy in place).

The approach

The brute force way is to try every pair of positions and check which swap produces the largest number. That works, but you can do it in a single pass with a greedy strategy.

The key insight: for each position from left to right, you want to know if there is a larger digit somewhere to its right. If there is, swap with the rightmost occurrence of the largest such digit. Why the rightmost? Because swapping with the rightmost occurrence keeps larger digits as far right as possible, which does not hurt your result, and it handles duplicates correctly.

The algorithm:

1. Record the last occurrence of each digit (0 through 9). A single pass through the number gives you a map from each digit value to the last index where it appears.

2. Scan left to right. For each digit, check if any larger digit (from 9 down to the current digit + 1) has a last occurrence to the right of the current position. If so, that is the optimal swap.

3. Swap and return. As soon as you find the first improvable position, swap it with the rightmost occurrence of the larger digit and return the result. If no swap improves the number, return it unchanged.

Brute force approach

Try every pair of indices and keep the maximum result. This is simple to implement but runs in O(n^2) time.

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

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

    return best

For each pair (i, j), you swap, check the value, and swap back. The outer loop runs n times and the inner loop runs up to n times, giving O(n^2) comparisons. This is fine for numbers with at most 8 digits (the constraint), but the greedy approach is cleaner and faster.

Optimal solution

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

    for i, d in enumerate(digits):
        for k in range(9, int(d), -1):
            if last.get(k, -1) > i:
                digits[i], digits[last[k]] = digits[last[k]], digits[i]
                return int("".join(digits))

    return num

The last dictionary maps each digit to its rightmost index. The outer loop scans left to right. For each position, the inner loop checks from 9 down to the current digit + 1. The moment it finds a larger digit whose last occurrence is to the right, it swaps and returns. If no swap is found after scanning every position, the number is already maximized.

Visual walkthrough

Let's trace through num = 2736 step by step.

The algorithm finds the answer in the first iteration of the outer loop. It checks index 0 (digit 2), discovers that 7 appears later at index 1, swaps them, and immediately returns 7236. No need to examine the rest of the digits.

Complexity

Time for the greedy approach is O(n). Building the last map is one pass through the digits. The nested loop looks like O(n * 10), but the inner loop always runs at most 10 iterations (digits 9 down to 0), so the total work is O(10n) which simplifies to O(n).

Space is O(1) beyond the digit array. The last map has at most 10 entries (one per digit 0 through 9), which is constant. The digit array itself is O(n), but you need it to manipulate the number regardless.

Edge cases

Already the maximum. When the digits are in non-increasing order like 9973, no swap can improve the number. The algorithm scans every position without finding a larger digit to the right, and returns the original number.

Duplicate digits. For 1993, the digit 9 appears at both index 1 and index 2. The last map records index 2 (the rightmost 9). When the algorithm checks index 0 (digit 1), it finds that 9 has a last occurrence at index 2 and swaps to get 9913. Using the rightmost occurrence is essential here. Swapping with index 1 would give 9193, which is smaller.

Single digit. A number like 5 has no pair to swap. The inner loop never finds a larger digit to the right, and the original number is returned.

Two identical digits. For 11, no swap changes the value. The algorithm correctly returns 11 because no digit from 9 down to 2 appears in the number.

All same digits. For 9999, every position already holds the maximum digit. No swap helps, and the number is returned as-is.

Building blocks

This problem is built from two reusable pieces that show up across many greedy and math problems.

Last occurrence tracking

Building a map from each value to its last (rightmost) index is a common preprocessing step. It lets you answer "does a larger value appear later?" in constant time. The same technique shows up in problems like Best Time to Buy and Sell Stock (tracking future maximums) and Next Greater Element (tracking positions of elements).

last = {int(d): i for i, d in enumerate(digits)}

This one-liner gives you O(1) lookups for where each digit last appears.

Greedy left-to-right scan

The idea of scanning left to right and making the locally optimal choice at each position is the core of many greedy algorithms. Here, you want to place the largest possible digit at the leftmost position that can be improved. Once you make that single swap, you are done. You never need to consider a second swap or backtrack.

From understanding to recall

You understand the greedy approach. You can see why tracking last occurrences works and why you scan from 9 downward. But can you write the solution from scratch without looking at the code?

The gap between "I get it" and "I can write it cold" is where most people stall. The last-occurrence map is a tiny piece. The scan-and-swap loop is another. Each piece takes under a minute to type. If you drill them separately with spaced repetition, you will not need to rederive the algorithm during your interview. You will just write it.

Related posts

• Reverse Integer - Another digit manipulation problem using mod/divide arithmetic. The same skill of thinking about individual digits transfers directly.
• Palindrome Number - Uses digit extraction to check if a number reads the same forward and backward. Another case where reasoning about digit positions is the key skill.
• Next Permutation - A greedy algorithm that scans from the right to find the optimal swap position. The structural similarity to Maximum Swap is strong: both problems find the best single change by looking at suffix properties.

CodeBricks breaks Maximum Swap into its last-occurrence tracking and greedy scan building blocks, then drills them with spaced repetition. You type each piece from scratch until it becomes automatic. When a digit manipulation problem shows up in your interview, you are not starting from zero.