Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The maximum and minimum are formed independently from the original number. The first changed digit dominates the result, so maximize the leftmost non-nine digit and minimize the earliest digit that can be reduced without creating a leading zero. Every occurrence of the chosen digit must change together.

Approach

For the maximum, replace all occurrences of the first non-nine digit with nine. For the minimum, if the leading digit is not one, replace all its occurrences with one. Otherwise replace the first digit other than zero or one, wherever it occurs, with zero. Leave a side unchanged when no improving digit exists. Convert both strings to integers and return their difference; neither transformation is applied on top of the other.

class Solution:
    def maxDiff(self, num: int) -> int:
        num = str(num)
        mx = '-1'
        mn = '-1'

        for c in num:
            if c != '9':
                mx = c
                break

        for c in num:
            if c != '1' and c != '0':
                mn = c
                break

        max_num = num if mx == '-1' else num.replace(mx, '9')
        min_num = num if mn == '-1' else num.replace(mn, '0') if num[0] != mn else num.replace(mn, '1')

        return int(max_num) - int(min_num)

Complexity analysis

For d decimal digits, locating replacement digits, performing at most two full replacements, and parsing results takes O(d) time and O(d) auxiliary string space.