Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The earliest improved digit dominates the value. To maximize, turn the first non-nine digit into nine everywhere. To minimize, turn the leading digit into zero everywhere; unlike related remapping problems, this task allows leading zeros in the resulting representation.

Approach

Create separate copies of the original decimal digits. In the maximum copy, replace every occurrence of the first non-nine digit with nine, leaving all-nine inputs unchanged. In the minimum copy, replace every occurrence of the original leading digit with zero. Convert both copies to integers and subtract the minimum from the maximum. The transformations are independent, and each consistently replaces all occurrences of its selected digit.

class Solution:
    def minMaxDifference(self, num: int) -> int:
        arr = list(str(num))
        n = len(arr)
        mx = ''
        mn = arr[0]

        for i in range(n):
            if arr[i] != '9':
                mx = arr[i]
                break

        mx_arr = arr[:]
        mn_arr = arr[:]

        for i in range(n):
            if mx_arr[i] == mx:
                mx_arr[i] = '9'
            if mn_arr[i] == mn:
                mn_arr[i] = '0'

        return int("".join(mx_arr)) - int("".join(mn_arr))

Complexity analysis

Let d be the number of decimal digits. Time: O(d). Auxiliary space: O(d) for digit arrays and rebuilt strings.