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) time complexity, which is acceptable for small inputs but inefficient for Amazon-scale data. Instead, I aim for an O(N) solution.
My strategy relies on the observation that to maximize the number, we should swap the leftmost digit that can be increased with the largest available digit appearing later in the sequence. If multiple instances of that largest digit exist, we pick the rightmost one to minimize disruption to higher place values.
First, I convert the integer to a character array or string for easy manipulation. I then create an auxiliary array of size 10 to store the last seen index of each digit from 0 to 9. As I iterate through the number, I update these indices. Once populated, I traverse the number again from left to right. For each digit at index i, I check digits greater than the current one, starting from 9 down to current_digit + 1. If I find a larger digit that appears later in the array, I perform the swap immediately and return the result. This greedy approach ensures the highest possible value is achieved with a single pass for recording and a second pass for decision-making, meeting Amazon's expectation for scalable, optimized code.
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
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.