670. Maximum Swap (Math, Greedy)

링크 - https://leetcode.com/problems/maximum-swap/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

1) Greedy Two-Pass

우리는 왼쪽부터 시작해서 오른쪽의 가장 큰 값이랑 바꿔 주면 된다는 점을 알고있다.

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

        # Start from right
        max_right_idx[n-1] = n-1
        # Going left
        for i in range(n-2, -1, -1):
            # e.g. 3->5->8->7
            # 8 is the maximum from its right so leave it as its idx
            # 5 has the maximum value 8 from its right so save its idx
            # 3 has the maximum value 8 from its right so save its idx
            max_right_idx[i] = (
                i
                if num_str[i] > num_str[max_right_idx[i+1]]
                else max_right_idx[i+1]
            )

        # Start from left and go right
        for i in range(n):
            # If there is maximum value from its right, change and return
            if num_str[i] < num_str[max_right_idx[i]]:
                num_str[i], num_str[max_right_idx[i]] = num_str[max_right_idx[i]], num_str[i]
                return int("".join(num_str))

        return num

Time Complexity: O(n)

Space Complexity: O(n)

2) Space Optimized Greedy

우리는 굳이 모든 index에 대한 max_right_idx를 저장할 필요가 없다. 오른쪽에서 왼쪽으로 가면서, 현재 인덱스가 가장 큰 값이면 max_digit_idx를 업데이트 해주고, 현재 인덱스가 max_digit_idx의 값보다 작으면 swap idx 두개를 업데이트 해 나간다. 그리고 swap을 해줘야하면 swap하고 종료한다.

class Solution:
    def maximumSwap(self, num: int) -> int:
        num_str = list(str(num))
        n = len(num_str)
        max_digit_idx = -1
        swap_idx1 = -1
        swap_idx2 = -1

        for i in range(n-1, -1, -1):
            if max_digit_idx == -1 or num_str[i] > num_str[max_digit_idx]:
                max_digit_idx = i
            elif num_str[i] < num_str[max_digit_idx]:
                swap_idx1 = i
                swap_idx2 = max_digit_idx

        if swap_idx1 != -1 and swap_idx2 != -1:
            num_str[swap_idx1], num_str[swap_idx2] = num_str[swap_idx2], num_str[swap_idx1]

        return int("".join(num_str))

Time Complexity: O(n)

Space Complexity: O(n)