• Posts

Problem 670 Maximum Swap

Problem Statement

Link - Problem 670

Question

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.

Example 1:

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

Example 2:

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

Constraints:

• 0 <= num <= 108

Solution

class Solution {
public:
    int maximumSwap(int num) {
        string numStr = to_string(num);
        int n = numStr.size();
        vector<int> maxRightIndex(n);

        maxRightIndex[n - 1] = n - 1;
        for (int i = n - 2; i >= 0; --i) {
            maxRightIndex[i] = (numStr[i] > numStr[maxRightIndex[i + 1]]) ? i: maxRightIndex[i + 1];
        }

        for (int i = 0; i < n; ++i) {
            if (numStr[i] < numStr[maxRightIndex[i]]) {
                swap(numStr[i],
                     numStr[maxRightIndex[i]]);
                return stoi(numStr);
            }
        }

        return num;
    }
};

Complexity Analysis

| Algorithm                                | Time Complexity | Space Complexity |
| ---------------------------------------- | --------------- | ---------------- |
| Two-pointer traversal with preprocessing | O(n)            | O(n)             |

Explanation

Intial Thoughts

To begin, break down the problem into smaller parts: converting the number to a string to easily access individual digits, then iterating through the digits from right to left to keep track of the maximum digit encountered so far. Consider using a data structure like a vector to store the indices of the maximum digits found so far. Think about how swapping two digits can affect the overall value of the number, focusing on maximizing the leftmost digits first. The goal is to find the first instance from the left where a smaller digit can be swapped with a larger one from the right. Start by considering extreme cases, such as numbers with all identical digits or numbers already in the maximum possible order.

Intuitive Analysis

Intuitively, the solution involves finding the first digit from the left that is smaller than the maximum digit to its right, because this is where swapping will have the greatest impact on the number’s value. Visualize the process as scanning the number from left to right while keeping track of the ‘best’ digit seen so far from the right. At each step, ask whether the current digit is less than the maximum digit found to its right, and if so, whether swapping them increases the number’s value. Consider the trade-offs between the positions of digits and their values, thinking about how moving a larger digit to the left can significantly increase the overall value. This process is akin to a greedy strategy where the goal is to maximize the value by making the optimal choice at each step without worrying about future steps.

1. Intuition

• The problem requires finding the maximum valued number that can be obtained by swapping two digits at most once.
• To achieve this, we need to identify the largest possible digit that can be swapped with the current digit to maximize the value.
• We should start from the rightmost digit and keep track of the maximum digit to its right.
• If the current digit is smaller than the maximum digit to its right, we can swap them to get a larger number.
• This approach ensures that we only need to make one pass through the digits to find the maximum valued number.
• The time complexity of this approach is O(n), where n is the number of digits in the input number.
• The space complexity is also O(n) due to the conversion of the integer to a string and the use of a vector to store the maximum right index.

2. Implementation

• The solution starts by converting the input integer num to a string numStr to easily access and manipulate individual digits.
• A vector maxRightIndex is used to store the index of the maximum digit to the right of each digit, initialized with the last index as n - 1.
• The maxRightIndex vector is populated by iterating through the digits from right to left, comparing each digit with the maximum digit to its right using numStr[i] > numStr[maxRightIndex[i + 1]].
• The solution then iterates through the digits from left to right, checking if the current digit is smaller than the maximum digit to its right using numStr[i] < numStr[maxRightIndex[i]].
• If a smaller digit is found, it is swapped with the maximum digit to its right using swap(numStr[i], numStr[maxRightIndex[i]]).
• After the swap, the modified string is converted back to an integer using stoi(numStr) and returned as the maximum valued number.
• If no swap is needed, the original input number is returned.

Complexity Analysis

Time Complexity:

• The algorithm involves two passes through the input string numStr. The first pass computes the maxRightIndex array, which takes O(n) time. The second pass iterates through numStr to find the swap point, also taking O(n) time. Since these passes are sequential, the overall time complexity is O(n) + O(n) = O(2n), which simplifies to O(n) because constant factors are ignored in Big O notation.
• The dominant operations are the two for loops that iterate through numStr and compute maxRightIndex. These loops are responsible for the linear time complexity.
• The Big O classification of O(n) is justified because the algorithm’s running time grows linearly with the size of the input num. This is evident from the two sequential passes through numStr, each taking time proportional to the length of numStr.

Space Complexity:

• The algorithm uses a maxRightIndex array of size n to store the indices of the maximum digits to the right of each position. This array requires O(n) space because its size grows linearly with the length of numStr.
• The input string numStr and the maxRightIndex array are the primary contributors to the space complexity. The numStr string requires O(n) space to store the digits of the input number, and the maxRightIndex array requires an additional O(n) space.
• The overall space complexity is O(n) because the algorithm uses a constant amount of space to store variables like i and n, and the space required by numStr and maxRightIndex dominates the overall memory usage.

Footnote

This question is rated as Medium difficulty.

Similar Questions: