Maximum Swap - Video Solutions

Problem Overview: You’re given a non‑negative integer. You may swap two digits at most once. The goal is to produce the largest possible number after that swap. If no beneficial swap exists, return the original number.

Approach 1: Brute Force Digit Swap (O(n^2) time, O(n) space)

Convert the number into a digit array so individual positions are easy to manipulate. Try every possible pair of indices (i, j) where i < j, swap the digits, and compute the resulting number. Track the maximum value across all swaps. After each test swap, revert the digits to continue exploring other combinations.

This works because there are only n(n-1)/2 possible swaps for n digits. However, recomputing the number after each swap makes the solution quadratic. It’s acceptable for small inputs but inefficient compared to a targeted strategy. Still, implementing this first often helps clarify the problem constraints before applying a greedy optimization.

Approach 2: Greedy Using Last Occurrence (O(n) time, O(1) space)

The key insight: for each digit, the best swap is with the largest possible digit that appears later in the number. Instead of testing all pairs, record the last occurrence index of each digit 0–9. This gives constant‑time access to the rightmost position of any digit.

Scan the digits from left to right. For the current digit d, check if a larger digit (from 9 down to d+1) appears later using the last‑occurrence map. If such a digit exists at position j > i, swapping digits[i] with digits[j] produces the largest improvement at the earliest place value. Perform the swap and stop immediately because only one swap is allowed.

This greedy rule works because improving a more significant digit always dominates any changes to less significant digits. By checking digits in descending order and using their last positions, you ensure the swap yields the maximum possible number. The algorithm runs in linear time and constant extra space, making it ideal for interview settings and large inputs. The reasoning relies on place value properties from math and a classic greedy choice strategy often used in array manipulation problems (arrays).

Recommended for interviews: The greedy last‑occurrence approach is the expected solution. It demonstrates recognition of the optimal swap position and reduces the search from quadratic to linear time. Mentioning the brute force method first shows problem exploration, while implementing the greedy version shows algorithmic maturity.