Jobs

Interviews

Discussions

Maximum Swap

Medium

Bloomberg LP

1 view

Topics:

ArraysGreedy Algorithms

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 <= 10⁸

Maximum Swap

Medium

Bloomberg LP

1 view

Topics:

ArraysGreedy Algorithms

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 <= 10⁸

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the digits in the input number?
Can the input number be zero? If so, what should the output be?
If multiple swaps result in the maximum possible value, which one should I return?
Is the input guaranteed to be a non-negative integer?
If no swap increases the value of the number, should I return the original number?

Brute Force Solution

Approach

The brute force approach to finding the maximum swap involves trying every possible pair of digits to swap. We explore all swap combinations and see which swap produces the largest possible number.

Here's how the algorithm would work step-by-step:

Consider each possible pair of digits in the number.
For each pair, imagine swapping them.
After swapping, compare the resulting number with the largest number we've seen so far.
If the new number is larger, remember it.
Repeat this process for all possible pairs of digits.
In the end, the largest number we remembered is the result of the maximum swap.

Code Implementation

def maximum_swap_brute_force(number):
    number_string = str(number)
    maximum_number = number

    # Iterate through all possible pairs of digits
    for first_index in range(len(number_string)):
        for second_index in range(first_index + 1, len(number_string)):

            # Convert the string to a list to allow swapping
            number_list = list(number_string)

            # Perform the swap
            number_list[first_index], number_list[second_index] = number_list[second_index], number_list[first_index]

            # Convert the list back to a string and then to an integer
            swapped_number = int("".join(number_list))

            # Check if this swap yields a larger number
            if swapped_number > maximum_number:
                maximum_number = swapped_number

    return maximum_number

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach involves checking every possible pair of digits within the number. With n digits, the outer loop iterates through each digit, and the inner loop compares it with every digit that comes after it. Therefore, the number of comparisons grows proportionally to n * (n-1) / 2. This simplifies to O(n²), representing quadratic time complexity.

Space Complexity

O(1) – The brute force approach described involves iterating through possible digit pairs and swapping them. It only uses a few variables to store indices of the digits being swapped and to keep track of the largest number found so far. The amount of extra memory used does not scale with the input number's size (N, representing the number of digits). Therefore, the space complexity is constant.

Optimal Solution

Approach

The most efficient way to solve this is to find the biggest digit to the right of each digit, and then swap. This avoids unnecessary checks and leads directly to the largest possible result. We prioritize finding the best possible swap early to maximize the number's value.

Here's how the algorithm would work step-by-step:

Look at the number from left to right, one digit at a time.
For each digit, find the largest digit that appears to its right.
If the largest digit to the right is bigger than the current digit, remember their positions.
After checking all digits, if you found a larger digit to swap with, swap the leftmost (earlier) current digit with its largest right-side digit.
If no swaps are possible, the number is already the largest possible.

Code Implementation

def maximum_swap(number):
    number_string = list(str(number))
    length_of_number = len(number_string)
    index_of_largest = -1
    index_to_swap_with = -1

    for current_index in range(length_of_number):
        largest_digit_index = current_index
        for right_index in range(current_index + 1, length_of_number):
            # Find the largest digit on the right
            if number_string[right_index] >= number_string[largest_digit_index]:
                largest_digit_index = right_index

        # Need to swap if a larger digit exists on the right.
        if number_string[largest_digit_index] > number_string[current_index]:
            index_of_largest = largest_digit_index
            index_to_swap_with = current_index
            break

    #If a swap can be made, then swap
    if index_of_largest != -1:
        number_string[index_of_largest], number_string[index_to_swap_with] = number_string[index_to_swap_with], number_string[index_of_largest]

    return int("".join(number_string))

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – We iterate through the digits of the number from left to right, which takes O(n) time, where n is the number of digits. For each digit, we find the largest digit to its right, also within O(n) in the worst case. However, finding the maximum to the right can be precomputed in O(n) using a single pass from right to left. After precomputation, the swap identification takes O(n). Thus, the dominant cost is still proportional to n.

Space Complexity

O(1) – The algorithm iterates through the digits of the number, maintaining a few variables to store the positions of the digits to be swapped. Specifically, it needs to store the index of the 'current digit' and the index of the 'largest digit to its right'. Since the number of such variables is constant and independent of the input size N (where N is the number of digits in the input number), the auxiliary space used is constant. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input string	Return the original string if the input is null or empty to avoid null pointer exceptions and handle trivial cases.
String of length 1	Return the original string as no swap is possible with a single character.
String with all identical characters (e.g., '1111')	Return the original string since no swap can increase the value.
Maximum-sized integer as a string (e.g., '9999999999')	Ensure the algorithm doesn't overflow when converting substrings to integers during the swap process (although we can assume it is not necessary for this question if we are swapping characters within the string).
String with leading zeros (e.g., '00123')	The algorithm should correctly handle leading zeros, comparing '0' with other digits without causing errors.
No possible swap leads to a larger number	The algorithm should iterate through all possible swaps and return the original string if no swap produces a larger number.
String representing a negative number	The algorithm should treat the minus sign as any other character (or, if we are told it is guaranteed to be a positive number, we don't handle it specifically).
Integer overflow if converting the string to an integer for comparison.	The algorithm avoids integer overflow by working directly on the string representation and comparing substrings instead of converting the entire string to an integer.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the digits in the input number?
Can the input number be zero? If so, what should the output be?
If multiple swaps result in the maximum possible value, which one should I return?
Is the input guaranteed to be a non-negative integer?
If no swap increases the value of the number, should I return the original number?

Brute Force Solution

Approach

The brute force approach to finding the maximum swap involves trying every possible pair of digits to swap. We explore all swap combinations and see which swap produces the largest possible number.

Here's how the algorithm would work step-by-step:

Consider each possible pair of digits in the number.
For each pair, imagine swapping them.
After swapping, compare the resulting number with the largest number we've seen so far.
If the new number is larger, remember it.
Repeat this process for all possible pairs of digits.
In the end, the largest number we remembered is the result of the maximum swap.

Code Implementation

def maximum_swap_brute_force(number):
    number_string = str(number)
    maximum_number = number

    # Iterate through all possible pairs of digits
    for first_index in range(len(number_string)):
        for second_index in range(first_index + 1, len(number_string)):

            # Convert the string to a list to allow swapping
            number_list = list(number_string)

            # Perform the swap
            number_list[first_index], number_list[second_index] = number_list[second_index], number_list[first_index]

            # Convert the list back to a string and then to an integer
            swapped_number = int("".join(number_list))

            # Check if this swap yields a larger number
            if swapped_number > maximum_number:
                maximum_number = swapped_number

    return maximum_number

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Look at the number from left to right, one digit at a time.
For each digit, find the largest digit that appears to its right.
If the largest digit to the right is bigger than the current digit, remember their positions.
After checking all digits, if you found a larger digit to swap with, swap the leftmost (earlier) current digit with its largest right-side digit.
If no swaps are possible, the number is already the largest possible.

Code Implementation

def maximum_swap(number):
    number_string = list(str(number))
    length_of_number = len(number_string)
    index_of_largest = -1
    index_to_swap_with = -1

    for current_index in range(length_of_number):
        largest_digit_index = current_index
        for right_index in range(current_index + 1, length_of_number):
            # Find the largest digit on the right
            if number_string[right_index] >= number_string[largest_digit_index]:
                largest_digit_index = right_index

        # Need to swap if a larger digit exists on the right.
        if number_string[largest_digit_index] > number_string[current_index]:
            index_of_largest = largest_digit_index
            index_to_swap_with = current_index
            break

    #If a swap can be made, then swap
    if index_of_largest != -1:
        number_string[index_of_largest], number_string[index_to_swap_with] = number_string[index_to_swap_with], number_string[index_of_largest]

    return int("".join(number_string))

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return the original string if the input is null or empty to avoid null pointer exceptions and handle trivial cases.
String of length 1	Return the original string as no swap is possible with a single character.
String with all identical characters (e.g., '1111')	Return the original string since no swap can increase the value.
Maximum-sized integer as a string (e.g., '9999999999')	Ensure the algorithm doesn't overflow when converting substrings to integers during the swap process (although we can assume it is not necessary for this question if we are swapping characters within the string).
String with leading zeros (e.g., '00123')	The algorithm should correctly handle leading zeros, comparing '0' with other digits without causing errors.
No possible swap leads to a larger number	The algorithm should iterate through all possible swaps and return the original string if no swap produces a larger number.
String representing a negative number	The algorithm should treat the minus sign as any other character (or, if we are told it is guaranteed to be a positive number, we don't handle it specifically).
Integer overflow if converting the string to an integer for comparison.	The algorithm avoids integer overflow by working directly on the string representation and comparing substrings instead of converting the entire string to an integer.