Problem of The Day: Maximum Swap

Problem Statement

Intuition

The problem asks to swap two digits in the given number to form the largest possible number. The key intuition is that we need to find the best pair of digits to swap by looking for the largest digit that can be placed earlier in the number to maximize the value.

Approach

1. Convert the number to a list of digits to manipulate them easily.
2. For each digit, check all the digits that come after it. Find the largest digit that is greater than the current digit.
3. Swap the current digit with this largest digit found.
4. If a swap is made, convert the list of digits back into a number and return it.
5. If no swap is needed, return the original number.

Complexity

• Time complexity:
  The time complexity is \(O(n^2)\), where \(n\) is the number of digits in the number. For each digit, we are checking all digits that come after it.
• Space complexity:
  The space complexity is \(O(n)\) for storing the digits of the number as a list.

Code

class Solution:
    def maximumSwap(self, num: int) -> int:
        nums = list(map(int, str(num)))
        N = len(nums)
        for i in range(N - 1):
            index = i + 1
            max_val = nums[i]
            for j in range(i + 1, N):
                if nums[i] < nums[j] and max_val <= nums[j]:
                    max_val = nums[j]
                    index = j
            if max_val > nums[i]:
                nums[i], nums[index] = nums[index], nums[i]
                break
        return int(''.join(map(str, nums)))

Editorial

Approach #1: Brute Force [Accepted]

def maximumSwap(self, num):
    A = list(str(num))
    ans = A[:]
    for i in range(len(A)):
        for j in range(i+1, len(A)):
            A[i], A[j] = A[j], A[i]
            if A > ans: ans = A[:]
            A[i], A[j] = A[j], A[i]

    return int("".join(ans))

• time: O(n^2)
• space: O(n)

Approach #2: Greedy [Accepted]

class Solution(object):
    def maximumSwap(self, num):
        A = map(int, str(num))
        last = {x: i for i, x in enumerate(A)}
        for i, x in enumerate(A):
            for d in xrange(9, x, -1):
                if last.get(d, None) > i:
                    A[i], A[last[d]] = A[last[d]], A[i]
                    return int("".join(map(str, A)))
        return num

• time: O(n)
• space: O(n)