Maximum Swap
Given a non-negative integer, you could swap at most two digits. Return the maximum valued number you can get.
Why Interviewers Ask This
Amazon interviewers ask this question to evaluate a candidate's ability to optimize brute-force logic into an efficient linear-time solution. They specifically test if you can identify that swapping the rightmost smaller digit with the largest available larger digit yields the optimal result, demonstrating strong analytical thinking and mastery of array traversal techniques.
How to Answer This Question
1. Clarify constraints: Confirm input is non-negative and determine if leading zeros are allowed after swapping. 2. Analyze edge cases: Consider single-digit numbers or already sorted descending sequences where no swap improves the value. 3. Propose a brute-force baseline: Briefly mention checking all pairs O(N^2) to show thoroughness, then pivot to optimization. 4. Design the linear approach: Explain your plan to store the last occurrence of each digit (0-9) in an array. Iterate through the number from left to right, checking if a larger digit exists later in the sequence. 5. Execute the swap logic: Upon finding the first position where a larger digit exists to the right, swap it with the largest such digit found at its last valid index. 6. Validate complexity: Explicitly state the time complexity is O(N) and space is O(1) since the digit storage is fixed size.
Key Points to Cover
- Demonstrate understanding of why a greedy approach works for maximizing numerical value
- Optimize from O(N^2) brute force to O(N) using a last-seen index array
- Correctly handle the edge case where the rightmost instance of the max digit must be chosen
- Clearly articulate time and space complexity analysis
- Show ability to translate mathematical logic into clean, production-ready code
Sample Answer
To solve the Maximum Swap problem efficiently, I would first analyze the goal: we want the largest possible number by swapping at most two digits. A naive approach would check every pair of indices, resulting in O(N^2) t…
Common Mistakes to Avoid
- Failing to check all digits greater than the current one when searching for a swap target
- Swapping with the first occurrence of a larger digit instead of the rightmost one
- Overlooking the constraint that only one swap is permitted
- Not handling single-digit numbers or already sorted descending inputs correctly
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.