LeetCode 1432 - Max Difference You Can Get From Changing an Integer

Difficulty: 🟡 Medium
Topics: Math, Greedy

Solution

Problem Understanding

The problem gives us an integer num, and we are allowed to perform a digit replacement operation twice, independently.

In one operation, we:

Choose a digit x
Choose another digit y
Replace every occurrence of digit x in the decimal representation of num with y

The two operations are completely independent. This means the second operation starts from the original num, not from the result of the first operation.

After performing the two operations, we obtain two numbers:

a, the result of the first replacement
b, the result of the second replacement

Our goal is to maximize:

a - b

There are two important restrictions:

Neither result may contain leading zeros
Neither result may become 0

The input size is very small, since:

1 <= num <= 10^8

This means the number has at most 9 digits, so even relatively inefficient solutions would still run quickly. However, the challenge is identifying the greedy structure that guarantees the maximum difference.

The key observation is that maximizing a - b means:

Make a as large as possible
Make b as small as possible

Since each operation is independent, we can optimize them separately.

Several edge cases are important:

A single digit number like 9
Numbers whose first digit is already 1
Numbers containing zeros
Cases where replacing a digit could create leading zeros
Cases where all digits are identical

For example, when minimizing a number, we cannot replace the leading digit with 0, because leading zeros are forbidden.

Approaches

Brute Force Approach

A brute force solution would try every possible replacement pair (x, y) for generating a, and every possible replacement pair (x, y) for generating b.

There are 10 possible digits for x and 10 for y, so each transformation has:

10 * 10 = 100

possible operations.

Since we need two independent operations, we could:

Generate all possible transformed values
Compute every possible difference
Return the maximum

This works because the search space is very small.

For each transformation:

Convert the number to a string
Replace all occurrences of x
Validate that the result has no leading zero and is not zero

Although feasible, this approach performs unnecessary work because the optimal transformation follows a very clear greedy pattern.

Optimal Greedy Approach

The optimal insight is that maximizing the difference can be separated into two independent greedy goals:

Construct the largest possible number
Construct the smallest possible number

To maximize the number:

Find the first digit that is not 9
Replace all occurrences of that digit with 9

Why does this work?

The leftmost digits contribute the most to the final value. Changing the first non-9 digit to 9 produces the largest increase.

To minimize the number:

There are two cases.

If the first digit is not 1:

Replace all occurrences of the first digit with 1

This reduces the most significant digit as much as possible without creating leading zeros.

If the first digit is already 1:

Find the first digit after the leading digit that is neither 0 nor 1
Replace all occurrences of that digit with 0

This minimizes the number while preserving validity.

This greedy strategy produces the optimal answer in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(100 × n)	O(n)	Tries every possible digit replacement
Optimal	O(n)	O(n)	Greedily constructs maximum and minimum values

Here, n is the number of digits in num.

Algorithm Walkthrough

Step 1: Convert the number to a string

Working with digits is much easier using string operations.

For example:

num = 9288
s = "9288"

Step 2: Construct the maximum possible number

We want the largest possible result.

Scan the string from left to right and find the first digit that is not 9.

Why the first one?

Because changing a more significant digit has a larger effect on the number.

Suppose we find digit 2.

Replace every occurrence of 2 with 9.

Example:

9288 -> 9988

If all digits are already 9, no change is needed.

Step 3: Construct the minimum possible number

Now we independently minimize the original number.

Case A: First digit is not `1`

The leading digit contributes the most to the number, so reducing it gives the largest decrease.

Replace every occurrence of the first digit with 1.

Example:

555 -> 111

We cannot use 0 because leading zeros are forbidden.

Case B: First digit is already `1`

We cannot reduce the leading digit further.

Now scan the remaining digits and find the first digit that is neither 0 nor 1.

Replace all occurrences of that digit with 0.

Example:

109090 -> 100000

This minimizes the number without introducing a leading zero.

Step 4: Compute the difference

Convert both transformed strings back to integers and return:

max_value - min_value

Why it works

The algorithm relies on positional digit importance.

A digit farther to the left contributes more to the total value than digits to the right. Therefore:

To maximize the number, we maximize the earliest possible digit
To minimize the number, we minimize the earliest possible digit without violating constraints

Because each replacement affects all occurrences of a digit, selecting the earliest beneficial digit guarantees the largest possible impact.

Python Solution

class Solution:
    def maxDiff(self, num: int) -> int:
        s = str(num)

        # Build maximum value
        max_s = s
        for ch in s:
            if ch != '9':
                max_s = s.replace(ch, '9')
                break

        # Build minimum value
        min_s = s

        if s[0] != '1':
            min_s = s.replace(s[0], '1')
        else:
            for ch in s[1:]:
                if ch != '0' and ch != '1':
                    min_s = s.replace(ch, '0')
                    break

        return int(max_s) - int(min_s)

The implementation begins by converting the integer into a string so digit replacements become straightforward.

For constructing the maximum value, the code scans from left to right looking for the first digit that is not 9. Once found, every occurrence of that digit is replaced with 9.

For constructing the minimum value, the code first checks the leading digit. If it is not 1, all occurrences of that digit are replaced with 1. Otherwise, the code searches the remaining digits for the first digit that is neither 0 nor 1, and replaces all occurrences of that digit with 0.

Finally, both transformed strings are converted back to integers and their difference is returned.

Go Solution

package main

import (
	"strconv"
	"strings"
)

func maxDiff(num int) int {
	s := strconv.Itoa(num)

	// Build maximum value
	maxS := s
	for _, ch := range s {
		if ch != '9' {
			maxS = strings.ReplaceAll(s, string(ch), "9")
			break
		}
	}

	// Build minimum value
	minS := s

	if s[0] != '1' {
		minS = strings.ReplaceAll(s, string(s[0]), "1")
	} else {
		for i := 1; i < len(s); i++ {
			if s[i] != '0' && s[i] != '1' {
				minS = strings.ReplaceAll(s, string(s[i]), "0")
				break
			}
		}
	}

	maxVal, _ := strconv.Atoi(maxS)
	minVal, _ := strconv.Atoi(minS)

	return maxVal - minVal
}

The Go implementation follows the same logic as the Python version. The main difference is the use of:

strconv.Itoa and strconv.Atoi for conversions
strings.ReplaceAll for digit replacement

Go strings are byte indexed, so accessing s[i] directly works safely because all characters are digits.

Integer overflow is not a concern because the constraints are small.

Worked Examples

Example 1

Input: num = 555

Construct Maximum

Step	Current String	Action
Start	555	Find first non-9 digit
Found `5`	555	Replace all `5` with `9`
Result	999	Maximum value

Construct Minimum

Step	Current String	Action
Start	555	First digit is not `1`
Replace `5` with `1`	111	Minimum value

Final computation:

999 - 111 = 888

Example 2

Input: num = 9

Construct Maximum

All digits are already 9.

max = 9

Construct Minimum

Leading digit is 9, not 1.

Replace all 9 with 1.

min = 1

Final computation:

9 - 1 = 8

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each digit is scanned a constant number of times
Space	O(n)	String copies are created during replacement

The algorithm performs only a few linear scans of the digit string. Since each replacement operation also takes linear time, the total complexity remains O(n).

The extra space comes from constructing transformed strings.

Test Cases

sol = Solution()

assert sol.maxDiff(555) == 888       # example case with all same digits
assert sol.maxDiff(9) == 8           # single digit case
assert sol.maxDiff(123456) == 820000 # general mixed digits
assert sol.maxDiff(10000) == 80000   # leading digit already 1
assert sol.maxDiff(909) == 898       # contains zeros
assert sol.maxDiff(111) == 888       # already minimal leading digit
assert sol.maxDiff(999999) == 888888 # already maximal number
assert sol.maxDiff(101) == 808       # no valid inner replacement except final digit
assert sol.maxDiff(1101057) == 8808050 # multiple zeros and ones
assert sol.maxDiff(8) == 7           # smallest non-1 single digit

Test	Why
`555`	All digits identical
`9`	Single digit maximum
`123456`	Standard mixed-digit case
`10000`	Leading digit already minimized
`909`	Contains zeros
`111`	All digits already `1`
`999999`	All digits already `9`
`101`	Minimal structure with zeros
`1101057`	Complex mixed digits
`8`	Small single digit input

Edge Cases

Single Digit Numbers

A single digit input such as 9 or 8 can be tricky because replacing digits may produce invalid results like 0.

The implementation handles this correctly by replacing the digit with 1 when minimizing. This guarantees the result remains nonzero and contains no leading zeros.

Numbers Starting With `1`

Inputs like 10023 are important because we cannot reduce the leading digit further without violating the no-leading-zero rule.

The algorithm correctly handles this by searching the remaining digits for the first digit that is neither 0 nor 1, then replacing it with 0.

Numbers Already Maximized

For inputs like 99999, there is no digit that can increase the number further.

The implementation detects this naturally because the scan for a non-9 digit fails, leaving the number unchanged.

Numbers Containing Many Zeros

Inputs like 909090 can cause bugs if replacements accidentally create leading zeros.

The algorithm never replaces the leading digit with 0, ensuring all transformed numbers remain valid.

LeetCode 1432 - Max Difference You Can Get From Changing an Integer

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Greedy Approach

Algorithm Walkthrough

Step 1: Convert the number to a string

Step 2: Construct the maximum possible number

Step 3: Construct the minimum possible number

Case A: First digit is not 1

Case B: First digit is already 1

Step 4: Compute the difference

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Construct Maximum

Construct Minimum

Example 2

Construct Maximum

Construct Minimum

Complexity Analysis

Test Cases

Edge Cases

Single Digit Numbers

Numbers Starting With 1

Numbers Already Maximized

Numbers Containing Many Zeros

Case A: First digit is not `1`

Case B: First digit is already `1`

Numbers Starting With `1`