Max Difference You Can Get From Changing an Integer: Greedy Digit Replacement

You are given an integer num. You will apply the following steps exactly two times: pick a digit x (0-9) that appears in the number, pick another digit y (0-9), and replace all occurrences of x with y in the number. The resulting number must not contain leading zeros and must not become 0. You perform this operation once to create a number a and once to create a number b. Return the maximum value of a - b.

This is LeetCode 1432: Max Difference You Can Get From Changing an Integer, a medium problem that tests your ability to think greedily about digits. The trick is figuring out the best digit to replace for both the maximum and minimum versions of the number.

Why this problem matters

Digit manipulation problems show up often in interviews, and they test a specific flavor of greedy thinking. Instead of choosing from a set of items or scheduling tasks, you are reasoning about how individual digits affect the magnitude of a number. The leftmost digit has the most impact, so greedy decisions start there. This same "most significant position first" reasoning appears in problems like Remove K Digits, Monotone Increasing Digits, and Largest Number.

The key insight

You need to make two separate numbers: one as large as possible (high) and one as small as possible (low).

To maximize: scan the digits left to right and find the first digit that is not already 9. Replace every occurrence of that digit with 9. This pushes the number as high as it can go, because you are boosting the most significant non-9 digit and all its copies.

To minimize: this is where it gets more nuanced due to the leading zero constraint.

• If the first digit is not 1, replace all occurrences of the first digit with 1. This makes the leading digit as small as possible without creating a leading zero.
• If the first digit is already 1, scan the remaining digits for the first one that is not 0 and not 1. Replace all occurrences of that digit with 0. You skip 0 and 1 because replacing a 0 does nothing useful, and replacing a 1 with 0 would turn the leading 1 into a leading 0.

The solution

def max_diff(num: int) -> int:
    s = str(num)

    # Build the high number
    for d in s:
        if d != '9':
            high = int(s.replace(d, '9'))
            break
    else:
        high = num

    # Build the low number
    if s[0] != '1':
        low = int(s.replace(s[0], '1'))
    else:
        for d in s[1:]:
            if d != '0' and d != '1':
                low = int(s.replace(d, '0'))
                break
        else:
            low = num

    return high - low

Here is what each section does:

1. Convert the number to a string so you can scan and replace individual digits.
2. High number: walk through the digits. The first digit that is not 9 becomes the target. Replace all of its occurrences with 9. If every digit is already 9, the high number is just num itself.
3. Low number: check the leading digit. If it is not 1, replace all of its occurrences with 1. If it is already 1, scan the remaining digits for the first one that is neither 0 nor 1, and replace all of its occurrences with 0. If no such digit exists (the number is already all 1s and 0s), the low number is num.
4. Return high - low.

Visual walkthrough

Let's trace through num = 555 step by step. The string representation is "555".

For the high number, the first digit is 5, which is not 9. Replace all 5s with 9 to get 999.

For the low number, the first digit is 5, which is not 1. Replace all 5s with 1 to get 111.

The difference is 999 - 111 = 888.

Now consider a trickier case: num = 1101057. The first digit is already 1, so you cannot just replace it. Scan the remaining digits: 1 (skip), 0 (skip, it is already 0), 1 (skip), 0 (skip), 5 (this is our target). Replace all 5s with 0 to get 1101007. For the high number, 1 is not 9, so replace all 1s with 9 to get 9909057. The answer is 9909057 - 1101007 = 8808050.

Complexity analysis

Where d is the number of digits. Converting to a string takes O(d), scanning for the target digit takes O(d), and str.replace takes O(d). You do this twice (once for high, once for low), but that is still O(d) overall. Space is O(d) for the string representation.

The building blocks

1. Greedy maximization by digit replacement

The pattern of scanning left to right and modifying the most significant position first is a core greedy strategy for number-building problems:

for digit in number_string:
    if digit != target_value:
        replace_all(digit, target_value)
        break

The leftmost non-optimal digit has the biggest impact on the total value. Fixing it first is always the right greedy choice. You see this same idea in Remove K Digits (remove the leftmost digit that breaks monotonicity) and Monotone Increasing Digits (find the leftmost violation and cascade downward).

2. Greedy minimization with leading zero avoidance

When minimizing a number by replacing digits, you face a constraint that does not exist when maximizing: the result cannot have a leading zero. This forces a two-case analysis:

if first_digit != min_safe_value:
    replace_first_digit_with(min_safe_value)
else:
    find_next_replaceable_digit_and_zero_it()

The "leading zero avoidance" pattern comes up any time you need to produce a valid number from digit-level operations. Recognizing it quickly saves you from subtle bugs.

Edge cases

Before submitting, make sure your solution handles these:

• Single digit num = 8: high = replace 8 with 9 = 9. Low = replace 8 with 1 = 1. Answer = 8.
• All same digits num = 555: high = 999, low = 111. Answer = 888.
• Already all 9s num = 999: high stays 999. For low, first digit is 9 (not 1), so replace all 9s with 1 = 111. Answer = 888.
• Leading 1 with all 0s and 1s num = 10100: high = replace 1 with 9 = 90900. For low, first digit is 1, and scanning the rest gives only 0s and 1s, so low stays 10100. Answer = 90900 - 10100 = 80800.
• Number is 10 num = 10: high = replace 1 with 9 = 90. Low = first digit is 1, scan rest, find 0 but it is already 0, so low = 10. Answer = 80.

From understanding to recall

You have read through the greedy digit replacement strategy and the two-case minimize logic. It makes sense. But the tricky part is remembering the minimize edge case during an interview: when the first digit is already 1, you need to skip both 0s and 1s while scanning for the target digit. That detail is easy to forget if you have not practiced it.

Spaced repetition closes that gap. You practice writing the two-case minimize logic from scratch at increasing intervals. After a few rounds, you do not need to re-derive the edge cases. You see "maximize minus minimize with digit replacement" and the code flows out, constraints and all.

The greedy digit strategy is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Reverse Integer - Another digit manipulation problem where you work with individual digits
• Palindrome Number - Working with digit-level representations to check properties
• Remove K Digits - Greedy digit removal to minimize a number

CodeBricks breaks the max difference LeetCode problem into its greedy digit replacement and leading zero avoidance building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a digit manipulation question shows up in your interview, you do not think about it. You just write it.