Maximum Swap
Asked at Apple
Problem
Given a non-negative integer, you can swap at most two digits to form the largest possible number. Return the maximum value you can obtain. The input is guaranteed to fit within a 32-bit signed integer.
Asked At
| Company | Difficulty | |
|---|---|---|
| Apple | MEDIUM | View all Apple questions → |
How to Think About It
Brute force: generate all possible swaps of two digits and track the maximum.
Think about what makes a swap beneficial: you want to move a larger digit to a more significant position.
Scan from left to right and record the last occurrence of each digit (0-9).
For each position, check if any larger digit exists to its right; if so, swap with the last such occurrence.
If no beneficial swap is found, the number is already maximal — return it as is.
Optimal Approach
Convert the number to a character array. Scan from right to left, tracking the index of the maximum digit seen so far. Simultaneously scan from left to right; at the first position where a smaller digit appears but a larger digit exists to its right, perform the swap and return. This greedy approach runs in O(n) time with O(1) space since digits are bounded 0-9.
What Trips People Up in Real Interviews
Clarify that at most two digits are swapped (exactly one swap or zero swaps if already optimal).
Edge case: single-digit numbers need no swap.
Edge case: numbers with all identical digits return unchanged.
Explain why tracking last occurrence of each digit avoids incorrect swaps when duplicates exist.
Walk through a trace with number 9973 → answer is 9973 (no improvement possible).
Solution Code
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 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 numFrequently Asked Questions
What is the Maximum Swap problem?
Given a non-negative integer, you can swap at most two digits to form the largest possible number. Return the maximum value you can obtain. The input is guaranteed to fit within a 32-bit signed integer.
How do you solve Maximum Swap?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Maximum Swap?
Maximum Swap is asked at Apple. It is a medium difficulty problem.
What are common mistakes on Maximum Swap?
- Clarify that at most two digits are swapped (exactly one swap or zero swaps if already optimal).
- Edge case: single-digit numbers need no swap.
- Edge case: numbers with all identical digits return unchanged.
- Explain why tracking last occurrence of each digit avoids incorrect swaps when duplicates exist.
- Walk through a trace with number 9973 → answer is 9973 (no improvement possible).