Leetcode 670. Maximum Swap
Problem Explanation
In the given problem, you are asked to return the maximum number that can be generated by swapping two digits in the given non-negative integer number. You are allowed to perform only one swap operation. If no swap operation can give a larger number, then the same number is returned.
For example,
-
Given the number
2736
, the maximum number that can be generated by performing one swap operation is7236
. This can be achieved by swapping the digits2
and7
. -
Given the number
9973
, no swap operation can give a larger number. Therefore,9973
is returned.
Solution Approach
A straightforward approach is to iterate through the digits in the given number from left to right. And for each digit, check whether there is a larger digit that occurs later in the number. If such a digit is found, perform a swap operation for those two digits and return the result.
The above approach can be efficiently implemented by:
-
Convert the integer into a string to access the digits of the number in constant time.
-
Create an array to keep track of the last index of each digit (from 0 to 9) in the number.
-
Traverse through the string, and for each digit, look for a larger digit that occurs later in the number. If such a digit is found, perform a swap operation and return the result.
This can be implemented using standard programming languages.
Python Solution
1 2python 3class Solution: 4 def maximumSwap(self, num: int) -> int: 5 # Convert the integer number into string 6 s = list(str(num)) 7 8 # Initialize an array to keep track of the last index of each digit 9 lastIndex = [0]*10 10 11 # Update the last index of each digit 12 for i, digit in enumerate(s): 13 lastIndex[int(digit)] = i 14 15 # Traverse through the string and look for the larger digit that comes later 16 for i, digit in enumerate(s): 17 for d in range(9, int(digit), -1): 18 if lastIndex[d] > i: 19 # Perform swap operation 20 s[i], s[lastIndex[d]] = s[lastIndex[d]], s[i] 21 return int(''.join(s)) 22 23 return num 24
Java Solution
1
2java
3class Solution {
4 public int maximumSwap(int num) {
5 // Convert the integer number into char array
6 char[] digits = Integer.toString(num).toCharArray();
7
8 // Initialize an array to keep track of the last index of each digit
9 int[] lastIndex = new int[10];
10
11 for (int i = 0; i < digits.length; i++) {
12 // Here we are calculating the distance from '0' ASCII value
13 lastIndex[digits[i] - '0'] = i;
14 }
15
16 for (int i = 0; i < digits.length; i++) {
17 // Here we are checking for all larger digits
18 for (int j = 9; j > digits[i] - '0'; j--) {
19 if (lastIndex[j] > i) {
20 // Swap the current and larger-digit's position
21 char tmp = digits[i];
22 digits[i] = digits[lastIndex[j]];
23 digits[lastIndex[j]] = tmp;
24
25 // Convert the char array back to an integer and return
26 return Integer.valueOf(String.valueOf(digits));
27 }
28 }
29 }
30 return num;
31 }
32}
JavaScript Solution
1
2javascript
3class Solution {
4 maximumSwap(num) {
5 // Convert the integer number into char array
6 let arr = Array.from(num.toString()).map(Number);
7
8 // Initialize an array to keep track of the last index of each digit
9 let lastIndex = new Array(10).fill(0);
10
11 for (let i = 0; i < arr.length; i++) {
12 // Update the last index of each digit
13 lastIndex[arr[i]] = i;
14 }
15
16 // Traverse through the char array
17 for (let i = 0; i < arr.length; i++) {
18 // Here we are checking for all larger digits
19 for (let j = 9; j > arr[i]; j--) {
20 if (lastIndex[j] > i) {
21 // Swap the current and larger-digit's position
22 [arr[i],arr[lastIndex[j]]] = [arr[lastIndex[j]],arr[i]];
23
24 // Convert the char array back to an integer and return
25 return parseInt(arr.join(''));
26 }
27 }
28 }
29
30 return num;
31 }
32};
The above solutions in Python, Java, and JavaScript follow a similar process:
- They all start by converting the input integer into a list of its digits. This allows simple and fast access to each digit for comparison and swapping.
- A "last index" array is created and populated, keeping track of the last occurrence of each digit (0-9) in the input number. This will be necessary when searching for possible swapping partners.
- Then, for each digit in the given number (from left to right):
- They look for a larger digit (from 9 to the current one) that occurs later in the list. This is done using the "last index" array.
- If such a digit is found, a swap is made, and the new number (result of the swap) is immediately returned.
- If no swaps were performed (i.e., the number is already the largest possible), the original number is returned.
These solutions all run in linear time (O(n)), where n is the number of digits in the input. This is because a constant amount of work is done for each digit (updating the "last index" array, looking for a larger digit and possibly swapping). Thus, these solutions offer a very efficient way to solve the problem.
All these implementations are straight-forward and idiomatic in their corresponding languages. They make good use of the built-in features of each language, such as list comprehensions and the map()
function in Python, ASCII manipulation in Java, and array destructuring (for swapping) in JavaScript.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.