Maximum Swap Problem

Problem

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.

Examples

Example 1:

1
2
3


Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2:

1
2
3


Input: num = 9973
Output: 9973
Explanation: No swap.

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Naive

The naive approach to solving this problem involves considering every possible pair of digits for swapping and determining which swap yields the maximum possible number. This is done by generating all possible numbers resulting from a single digit swap and then selecting the largest one. Here is the approach:

Convert the number to a list of digits: This allows for easy manipulation of individual digits.
Generate all possible swaps:
- Iterate through the list of digits with two nested loops to check every possible pair of digits for swapping.
- For each pair, swap the digits and generate the resulting number.
- Record the maximum number obtained through all possible swaps.
Return the maximum number:
- After evaluating all potential swaps, return the maximum number obtained.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution {
    public int maximumSwap(int num) {
        char[] digits = Integer.toString(num).toCharArray();
        int n = digits.length;
        int maxNum = num;

        // Generate all possible swaps
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Swap digits
                char temp = digits[i];
                digits[i] = digits[j];
                digits[j] = temp;
                // Convert array back to number
                int newNum = Integer.parseInt(new String(digits));
                // Update maxNum if newNum is greater
                maxNum = Math.max(maxNum, newNum);
                // Swap back to restore the original digits
                temp = digits[i];
                digits[i] = digits[j];
                digits[j] = temp;
            }
        }

        return maxNum;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution:
    def maximumSwap(self, num: int) -> int:
        digits = list(str(num))
        n = len(digits)
        max_num = num

        # Generate all possible swaps
        for i in range(n):
            for j in range(i + 1, n):
                # Swap digits
                digits[i], digits[j] = digits[j], digits[i]
                # Convert list back to number
                new_num = int("".join(digits))
                # Update max_num if new_num is greater
                max_num = max(max_num, new_num)
                # Swap back to restore the original digits
                digits[i], digits[j] = digits[j], digits[i]

        return max_num

Complexity

⏰ Time complexity: O(n^2), where n is the number of digits in the number. This is because we consider every possible pair of digits for swapping, resulting in n * (n - 1) / 2 possible swaps.
🧺 Space complexity: O(n) for storing the digits and intermediate results.

Method 2 - Two Pass

To achieve the maximum possible number, we need to identify the best two digits to swap. Now, for that we need the largest number at some least significant position to move to most significant position. So, for each digit, find the largest possible digit that can be swapped with it from the right side. To find the max element, we can traverse the array from the right.

For finding the digit to be swapped, we traverse the number from left to right. For each digit, check if swapping it with any larger digit on the right side results in a greater number.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution {
    public int maximumSwap(int num) {
        char[] digits = Integer.toString(num).toCharArray();
        int n = digits.length;

        // Track the index of the largest digit from right to left
        int[] maxIdx = new int[n];
        maxIdx[n - 1] = n - 1;
        for (int i = n - 2; i >= 0; i--) {
            if (digits[i] > digits[maxIdx[i + 1]]) {
                maxIdx[i] = i;
            } else {
                maxIdx[i] = maxIdx[i + 1];
            }
        }

        // Find the first digit that can be swapped for a larger digit on the right
        for (int i = 0; i < n; i++) {
            if (digits[i] != digits[maxIdx[i]]) {
                // Swap the digits
                char temp = digits[i];
                digits[i] = digits[maxIdx[i]];
                digits[maxIdx[i]] = temp;
                break;
            }
        }

        return Integer.parseInt(new String(digits));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution:
    def maximumSwap(self, num: int) -> int:
        digits = list(str(num))
        n = len(digits)

        # Track the largest digit from right to left
        max_idx = [0] * n
        max_idx[-1] = n - 1

        for i in range(n - 2, -1, -1):
            if digits[i] > digits[max_idx[i + 1]]:
                max_idx[i] = i
            else:
                max_idx[i] = max_idx[i + 1]

        # Find the first place where the current digit is less than max digit
        for i in range(n):
            if digits[i] != digits[max_idx[i]]:
                # Swap the digits
                digits[i], digits[max_idx[i]] = digits[max_idx[i]], digits[i]
                break

        return int("".join(digits))

Complexity

⏰ Time complexity: O(n), where n is the number of digits in the given number. We traverse the digits a few times in linear time.
🧺 Space complexity: O(n) for storing the digits and for tracking the largest digits.

Method 3 - One pass

Achieve the maximum number by swapping two digits with the goal of maximizing the value.
Loop from end to start to track the largest digit from the rightmost end towards the start.

Here is the approach:

Convert the number to a string and then to a list of digits for easy manipulation.
Initialize variables to keep track of:
- The maximum digit encountered so far from the right (maxDigit).
- The index of this maximum digit (maxDigitIndex).
- The position of the digits to be swapped to achieve the maximum value (swapWith and swapTo).
Traverse the list once:
- Update the maxDigit and maxDigitIndex when we encounter a new maximum digit.
- For digits that are less than maxDigit encountered so far, update the swapWith and swapTo indices to record the best possible swap.
Perform the swap if a valid one is identified.
Convert the updated list back to a number and return it.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


class Solution {
    public int maximumSwap(int num) {
        char[] digits = Integer.toString(num).toCharArray();
        int n = digits.length;

        // Initialize variables to track the best swap positions
        int maxDig = -1;
        int maxDigIdx = -1;
        int leftIdx = -1;
        int rightIdx = -1;

        // Traverse the array of digits from end to start
        for (int i = n - 1; i >= 0; i--) {
            // Update maxDig and its index if we find a new max
            if (digits[i] > maxDig) {
                maxDig = digits[i];
                maxDigIdx = i;
            }
            
            // If current digit is smaller than maxDig, we potentially found a better swap
            if (digits[i] < maxDig) {
                leftIdx = i;
                rightIdx = maxDigIdx;
            }
        }

        // Perform the swap if a valid leftIdx and rightIdx are found
        if (leftIdx != -1) {
            char temp = digits[leftIdx];
            digits[leftIdx] = digits[rightIdx];
            digits[rightIdx] = temp;
        }

        // Convert back to integer and return
        return Integer.parseInt(new String(digits));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution:
    def maximumSwap(self, num: int) -> int:
        digits = list(str(num))
        n = len(digits)

        # Initialize variables to track the best swap positions
        maxDig = -1
        maxDigIdx = -1
        leftIdx = -1
        rightIdx = -1

        # Traverse the list of digits from end to start
        for i in range(n - 1, -1, -1):
            # Update maxDig and its index if we find a new max
            if digits[i] > maxDig:
                maxDig = digits[i]
                maxDigIdx = i

            # If current digit is smaller than maxDig, we potentially found a better swap
            if digits[i] < maxDig:
                leftIdx = i
                rightIdx = maxDigIdx
        
        # Perform the swap if a valid leftIdx and rightIdx are found
        if leftIdx != -1:
            digits[leftIdx], digits[rightIdx] = digits[rightIdx], digits[leftIdx]
        
        # Convert back to integer and return
        return int("".join(digits))

Complexity

⏰ Time complexity: O(n), where n is the number of digits in the given number. This is because we perform a single pass over the digits.
🧺 Space complexity: O(n) for storing the digits.

Problem#

Examples#

Solution#

Video explanation#

Method 1 - Naive#

Code#

Complexity#

Method 2 - Two Pass#

Code#

Complexity#

Method 3 - One pass#

Code#

Complexity#

Problem

Examples

Solution

Video explanation

Method 1 - Naive

Code

Complexity

Method 2 - Two Pass

Code

Complexity

Method 3 - One pass

Code

Complexity