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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Swap

Number: 670

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Google, Microsoft, TikTok, KLA

Problem Description

Given a non-negative integer, perform at most one swap of two digits to obtain the maximum possible number. If no swap can increase the number's value, return the original number.

Key Insights

  • Use a greedy strategy to get the highest value number.
  • Record the last occurrence index of each digit (0 through 9) in the number.
  • Iterate through the digits. For each digit, check if there is a larger digit available later in the number.
  • Swap the current digit with the rightmost occurrence of the larger digit if it makes the entire number larger.
  • Only one swap is allowed, so the first valid swap is the optimal solution.

Space and Time Complexity

Time Complexity: O(n) where n is the number of digits (since we scan the digits a constant number of times). Space Complexity: O(n) for storing the digits and the occurrence mapping.

Solution

We first convert the input number into a list (or equivalent structure) of digits. Then, we create a mapping of each digit (0-9) to its last occurrence index in the list. The key idea is that for each digit (from leftmost to rightmost), we look for a larger digit that occurs later. Starting from 9 down to one greater than the current digit, we check if such a digit exists in the mapping at an index beyond the current position. If found, we swap and return the new number immediately. If no such digit is found for any position, the number is already maximized, so we return the original number.

Code Solutions

def maximumSwap(num):
    # Convert number to a list of characters (digits)
    digits = list(str(num))
    # Create a mapping of the last occurrence of each digit
    last = {int(digit): index for index, digit in enumerate(digits)}
    
    # Iterate over the digits from left to right
    for i, digit in enumerate(digits):
        # Check for a digit larger than the current one from 9 down to current+1
        for d in range(9, int(digit), -1):
            # If a larger digit appears later in the number, swap and return result
            if last.get(d, -1) > i:
                digits[i], digits[last[d]] = digits[last[d]], digits[i]
                return int("".join(digits))
    return num

# Test example
print(maximumSwap(2736))  # Expected output: 7236
← Back to All Questions