Maximum Swap

Maximum Swap

1. What is this problem about?

The Maximum Swap problem asks you to take a non-negative integer and perform at most one swap between two digits to make the resulting number as large as possible. For example, if you have the number 2736, you can swap the '2' and the '7' to get 7236, or swap the '2' and the '6' to get 6732. The goal is to identify the single best swap that maximizes the final value.

2. Why is this asked in interviews?

This "Maximum Swap interview question" is a favorite for companies like Microsoft, Meta, and TikTok. It tests a candidate's ability to handle greedy logic and digit manipulation. It evaluates whether you can recognize that the best swap involves moving a large digit from a low-significance position (right side) to a high-significance position (left side), but only if that larger digit is greater than the digit currently in that higher position.

3. Algorithmic pattern used

The "Math, Greedy interview pattern" involves recording the last occurrence of each digit (0-9). You iterate through the number from left to right. For each digit at position i, you check if there exists a larger digit (from 9 down to current_digit + 1) that appears at a position j where j > i. If such a digit exists, you swap the digit at i with the last occurrence of that larger digit and return the result immediately.

4. Example explanation

Number: 1993

• Digits: [1, 9, 9, 3]
• Last seen positions: {1:0, 9:2, 3:3} (Note: '9' is last seen at index 2).
• Index 0: Digit '1'. Is there a digit larger than 1 to the right? Yes, '9'. The last '9' is at index 2.
• Swap index 0 and index 2: [9, 9, 1, 3] -> 9913. The result is 9913. If we swapped the first '9', we'd get 9193, which is smaller.

5. Common mistakes candidates make

In the "Maximum Swap coding problem," a common mistake is swapping the first occurrence of a larger digit instead of the last occurrence. In the example 1993, swapping the 1 with the first 9 gives 9193, while swapping with the last 9 gives 9913. Another error is not stopping after the first valid swap is found—remember, the problem specifies "at most one swap." Some candidates also struggle with converting between integers and strings/lists of digits efficiently.

6. Interview preparation tip

Practice "digit-by-digit" thinking. Many number-based problems are easier to solve if you treat the number as a list of characters or integers. Specifically for this problem, remember that to make a number larger, you want the change to happen as far to the "left" as possible. Once you find the leftmost digit that can be replaced by a larger digit from its right, you have found the optimal swap point.