Thomas Ngo

Software Engineer

3 minute read

Problem Statement

problem

Intuition

The problem asks for the largest possible number that can be obtained by swapping two digits of a given integer. To solve this, the first thought is to find the best two digits to swap, such that the resulting number is maximized. Ideally, we should try to bring the largest possible digit to the most significant position.

Approach

  1. Decomposition into digits: First, we decompose the number into its digits and store them in a deque. This helps in accessing the digits easily from both ends.

  2. Tracking the largest digits: A max-heap is used to store the digits along with their indices. Since we are aiming to maximize the number, the max-heap allows us to always get the largest digit that hasn’t been swapped yet.

  3. Swapping for maximization: For each digit (starting from the most significant position), we check if there is a larger digit available at a later position. If such a digit is found, we perform the swap and immediately compute the new number formed by the updated digits.

  4. Heap management: The heap helps efficiently track the largest digit, and we use the digit’s index to compare with the current digits.

  5. Return the largest number: If no beneficial swap can be made, we return the original number.

Complexity

  • Time complexity:
    The time complexity is dominated by the need to traverse the digits and manage the max-heap. Building the max-heap takes \(O(n \log n)\), where \(n\) is the number of digits in the number. Thus, the overall time complexity is \(O(n \log n)\).
  • Space complexity:
    The space complexity is \(O(n)\), where \(n\) is the number of digits, because of the storage used for the deque and the max-heap.

Code

class Solution:
    def maximumSwap(self, num: int) -> int:
        temp = num
        max_heap = []
        queue = deque()
        i = -1
        while num > 0:
            digit = num % 10
            heapq.heappush(max_heap, (-digit, -i, i))
            num = num // 10
            i -= 1
            queue.appendleft(digit)

        N = len(queue)
        while max_heap:
            digit, _, i = heapq.heappop(max_heap)
            digit *= -1
            for j in range(0, N + i + 1):
                if queue[j] < digit:
                    queue[i], queue[j] = queue[j], queue[i]
                    ret = 0
                    for x in queue:
                        ret = ret * 10 + x
                    return ret

        return temp

Editorial

Approach 2: Greedy Two-Pass

class Solution:
    def maximumSwap(self, num: int) -> int:
        num_str = list(str(num))
        n = len(num_str)
        max_right_index = [0] * n

        max_right_index[n - 1] = n - 1
        for i in range(n - 2, -1, -1):
            max_right_index[i] = (
                i
                if num_str[i] > num_str[max_right_index[i + 1]]
                else max_right_index[i + 1]
            )

        for i in range(n):
            if num_str[i] < num_str[max_right_index[i]]:
                num_str[i], num_str[max_right_index[i]] = (
                    num_str[max_right_index[i]],
                    num_str[i],
                )
                return int("".join(num_str))

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

Approach 3: Suboptimal Greedy

class Solution:
    def maximumSwap(self, num: int) -> int:
        num_str = str(num)
        n = len(num_str)
        last_seen = [-1] * 10  # Store the last occurrence of each digit

        # Record the last occurrence of each digit
        for i in range(n):
            last_seen[int(num_str[i])] = i

        # Traverse the string to find the first digit that can be swapped with a larger one
        for i in range(n):
            for d in range(9, int(num_str[i]), -1):
                if last_seen[d] > i:
                    # Perform the swap
                    num_str = list(num_str)
                    num_str[i], num_str[last_seen[d]] = (
                        num_str[last_seen[d]],
                        num_str[i],
                    )
                    num_str = "".join(num_str)

                    return int(
                        num_str
                    )  # Return the new number immediately after the swap

        return num  # Return the original number if no swap can maximize it

Approach 4: Space Optimized Greedy

class Solution:
    def maximumSwap(self, num: int) -> int:
        num_str = list(str(num))
        n = len(num_str)
        max_digit_index = -1
        swap_idx_1 = -1
        swap_idx_2 = -1

        # Traverse the string from right to left, tracking the max digit and
        # potential swap
        for i in range(n - 1, -1, -1):
            if max_digit_index == -1 or num_str[i] > num_str[max_digit_index]:
                max_digit_index = i  # Update the index of the max digit
            elif num_str[i] < num_str[max_digit_index]:
                swap_idx_1 = i  # Mark the smaller digit for swapping
                swap_idx_2 = (
                    max_digit_index  # Mark the larger digit for swapping
                )

        # Perform the swap if a valid swap is found
        if swap_idx_1 != -1 and swap_idx_2 != -1:
            num_str[swap_idx_1], num_str[swap_idx_2] = (
                num_str[swap_idx_2],
                num_str[swap_idx_1],
            )

        return int(
            "".join(num_str)
        )  # Return the new number or the original if no
        # swap occurred

You may also enjoy