Maximize number with one digit swap
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a non-negative integer n (as an int or string), perform at most one swap of two digits to produce the maximum possible value. Return the resulting integer. Design an O(L) algorithm (L = number of digits) using last-occurrence tracking of digits and scan from most significant to least significant. Include an early exit when the current digit is already the largest available to its right and no better swap exists.
Quick Answer: Maximize number with one digit swap evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Given a non-negative integer `n`, you may swap two digits at most once to get the maximum valued number. Return the maximum valued number you can get.
Design an O(L) algorithm (L = number of digits): record the last occurrence of each digit 0-9, then scan from the most significant digit to the least. For each digit, look for the largest digit (9 down to current+1) whose last occurrence lies to its right; the first such swap produces the lexicographically largest result, so perform it and stop. If no beneficial swap exists, return the number unchanged.
Example 1: n = 2736 -> 7236 (swap the 2 and the 7).
Example 2: n = 9973 -> 9973 (the number is already maximal, no swap improves it).
Constraints
- 0 <= n <= 10^9 (fits in a 32-bit int for the typed signatures).
- Leading zeros are not introduced into the integer return value (e.g. 120 -> 210, never 021).
- At most one swap of two digit positions is allowed.
- If no swap increases the value, the original number is returned unchanged.
Examples
Input: (2736,)
Expected Output: 7236
Explanation: Swap the leading 2 with the rightmost larger digit 7 to get 7236.
Input: (9973,)
Expected Output: 9973
Explanation: Already maximal; every digit is >= those to its right, so no swap improves it.
Hints
- Track the last (rightmost) index at which each digit 0-9 appears. Choosing the rightmost occurrence of a larger digit maximizes the gain when you swap it forward.
- Scan digits left to right (most significant first). The first position where a strictly larger digit exists somewhere to its right is where the optimal swap happens.
- For the current digit, search candidate digits from 9 down to current+1; take the first whose last occurrence is to the right, swap, and return immediately.
- Early exit: if a digit is already the largest available to its right, no swap there helps, so move on; once you make any swap you are done.