Sponsored
Sponsored
The idea is to always try and bring the largest possible digit to the leftmost position if it maximizes the number. For this, we can use a map to record the last occurrence of each digit. By iterating through the number, we can then attempt swapping if any larger digit occurs later.
Time Complexity: O(n), where n is the number of digits in num.
Space Complexity: O(1) as the storage is constant due to limited digit size.
1public class Solution {
2 public int maximumSwap(int num) {
3 char[] digits = Integer.toString(num).toCharArray();
4 int[] last = new int[10];
5
6 for (int i = 0; i < digits.length; i++) {
7 last[digits[i] - '0'] = i;
8 }
9
10 for (int i = 0; i < digits.length; i++) {
11 for (int d = 9; d > digits[i] - '0'; d--) {
12 if (last[d] > i) {
13 char tmp = digits[i];
14 digits[i] = digits[last[d]];
15 digits[last[d]] = tmp;
16 return Integer.parseInt(new String(digits));
17 }
18 }
19 }
20 return num;
21 }
22
23 public static void main(String[] args) {
24 Solution sol = new Solution();
25 int num = 2736;
26 System.out.println(sol.maximumSwap(num));
27 }
28}The Java solution transforms the number into a character array for easy manipulation. It maintains an array of the last occurrences of each digit, and swaps appropriately to achieve the maximum number.