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,

  1. Given the number 2736, the maximum number that can be generated by performing one swap operation is 7236. This can be achieved by swapping the digits 2 and 7.

  2. 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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.


TA 👨‍🏫