algoadvance

Leetcode 670. Maximum Swap

Problem Statement

You are given a non-negative integer num represented as a string. You can swap any two digits at most once to get the maximum valued number. Return the maximum valued number you can get.

Clarifying Questions

1. Input Range:
   • What is the range of the input num?
   • Is the number guaranteed to be non-negative?
2. Format:
   • Can num be an empty string, or is it always guaranteed to be at least one digit long?
   • Should we assume input to be always valid (i.e., consisting only of digits)?
3. Output:
   • Should the output be an integer or a string representing the maximum number?

Given we assume:

• num is a non-negative integer represented as a string.
• The length of num is at least 1.

Strategy

1. Locate Highest Possible Swap:
   • Traverse the number from left to right.
   • For each digit, check all the subsequent digits to find the largest possible digit to swap with.
   • If a larger digit is found later in the number, swap these two digits.
2. Implementation Steps:
   • Convert num to vector<char> for easier manipulation.
   • Iterate through the vector to find the highest value for a possible swap.
   • Execute the swap if found and convert the vector back to a string for the result.
3. Time Complexity:
   • The solution involves nested loops where each digit is compared with those that come after it.
   • This results in O(n^2) time complexity, where n is the number of digits in num.
   • This can be improved by storing and updating the last occurrence of each digit to reduce unnecessary comparisons.

Code

Here is the C++ implementation of the described strategy:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string maximumSwap(string num) {
    vector<int> last(10, -1);  // to record the last position of digit 0 - 9
    
    // Record the last appearance of each digit
    for (int i = 0; i < num.size(); i++) {
        last[num[i] - '0'] = i;
    }

    // Traverse the number to find the first digit that can be swapped to get a larger number
    for (int i = 0; i < num.size(); i++) {
        for (int d = 9; d > num[i] - '0'; d--) {
            if (last[d] > i) {
                // A larger digit found, swap
                swap(num[i], num[last[d]]);
                return num;
            }
        }
    }
    
    // If no swap needed, return original
    return num;
}

// Testing the function
int main() {
    cout << maximumSwap("2736") << endl;  // Expected output: 7236
    cout << maximumSwap("9973") << endl;  // Expected output: 9973
    return 0;
}

Explanation

• Recording Last Positions: We use an array last to store the last occurrence of each digit from 0 to 9 in the string.
• Iterative Checking: For each digit in the string, starting from the left, we check from digit 9 down to one higher than the current digit to see if there is a higher-valued digit that appears later in the string.
• Swapping: If we find such a digit, we swap it with the current digit and return the result.
• Early Return: As soon as a swap is made, the algorithm returns the modified number since there is no need to perform further swaps.

This approach ensures that we maximize the number with the least computational effort possible given the constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?