We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

Maximum Swap

Difficulty: Medium

Problem Description

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.

Key Insights

The goal is to make the largest possible number by swapping two digits.
A greedy approach can be used to find the optimal swap.
We need to be mindful of the digit positions to maximize the resultant number.

Space and Time Complexity

Time Complexity: O(n), where n is the number of digits in the number. Space Complexity: O(n), for storing the digits in a list.

Solution

To solve the problem, we can follow these steps:

Convert the integer into a list of its digits for easier manipulation.
Create a mapping of the last occurrence of each digit to quickly find the best candidate to swap.
Traverse the digits from left to right. For each digit, check if there is a larger digit available to the right that can be swapped to form a larger number.
If a suitable swap is found, perform the swap and return the new number.

Code Solutions

def maximumSwap(num):
    # Convert the number into a list of its digits
    digits = list(str(num))
    # Create a dictionary to track the last position of each digit
    last = {int(d): i for i, d in enumerate(digits)}
    
    # Traverse the digits to find the best candidates for swapping
    for i in range(len(digits)):
        # Check from 9 to the digit at position i
        for d in range(9, int(digits[i]), -1):
            # If a larger digit exists, swap them
            if d in last and last[d] > i:
                # Perform the swap
                digits[i], digits[last[d]] = digits[last[d]], digits[i]
                # Return the maximum number formed
                return int(''.join(digits))
    
    # If no swap was made, return the original number
    return num

← Back to All Questions