Maximize number with one digit swap

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.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Maximize Number with One Digit Swap

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.

Hints

1. 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.
2. 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.
3. 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.
4. 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.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

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.

Recommended Approach

Record the last occurrence of each digit 0-9. Scan digits from left to right; for the current digit d, look for a larger digit from 9 down to d+1 whose last occurrence is to the right. The first such swap yields the lexicographically largest possible number, so perform it and stop.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

Time: O(L * 10) = O(L). Space: O(1).

Edge Cases and Tests

Already maximal number, repeated digits, leading digit swaps, single digit, all equal digits, and string input that may exceed integer range.