Swap two digits at most once in a number to maximize it. Return the max result.
Input: num=2736 → Output: 7236. Swap 7 and 2.
Input: num=9973 → Output: 9973
Record last occurrence of each digit 0-9. For each digit from left, check if a larger digit appears later.
- Convert to char array
- Record last index of each digit 0-9
- For each position from left
- Check digits 9 down to current+1
- If larger digit exists later, swap and return
- Return original number
public int maximumSwap(int num) {
char[] digits = Integer.toString(num).toCharArray();
int[] last = new int[10];
for (int i = 0; i < digits.length; i++) last[digits[i] - '0'] = i;
for (int i = 0; i < digits.length; i++) {
for (int d = 9; d > digits[i] - '0'; d--) {
if (last[d] > i) {
char tmp = digits[i];
digits[i] = digits[last[d]];
digits[last[d]] = tmp;
return Integer.parseInt(new String(digits));
}
}
}
return num;
}
- Time Complexity: O(n)
- Space Complexity: O(1)