DSA problem
Maximum Swap
You are given an integer num. You can swap two digits at most once to get the maximum valued number. Return the maximum valued number you can get.
A brute-force solution tries every pair of digit positions and keeps the best resulting number. With d digits this is O(d^2) swaps, each generating a number we compare to the running best — fine for the tiny input bound but unsatisfying because it ignores the obvious greedy structure of the problem.
The greedy insight is that a beneficial swap moves a large digit leftward into the position of a smaller digit. To maximize the result, we want the leftmost place where we can place a strictly larger digit. So for each position i from left to right, we ask: somewhere to the right of i, is there a digit strictly greater than s[i]? If yes, swap s[i] with the rightmost occurrence of the largest such digit (rightmost so that, among equal large digits, we keep low-value ones up front in the trailing portion).
To do this in a single pass, precompute maxRight[i] = index of the maximum digit in s[i..n - 1] (ties broken by latest index). Then sweep i left to right; the first index where s[maxRight[i + 1]] > s[i] is the swap target. One swap, return the result. This runs in O(d) time and O(d) space, both linear in the number of digits.
Examples
num = 27367236num = 99739973num = 9836898863Constraints
- 0 <= num <= 10^8
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.