LeetCode 2566 - Maximum Difference by Remapping a Digit

Difficulty: 🟢 Easy
Topics: Math, Greedy

Solution

Problem Understanding

The problem asks us to maximize the difference between two numbers that can be created from a given integer num through a specific remapping operation.

We are allowed to choose exactly one digit d1 from 0 through 9, and replace all occurrences of that digit in num with another digit d2, which can also be any digit from 0 through 9. Importantly, d1 and d2 may be the same digit, meaning the number does not have to change.

The task is to compute:

maximum possible remapped value - minimum possible remapped value

The remapping used to obtain the maximum value and the remapping used to obtain the minimum value are completely independent. We can choose different source and target digits for each.

A crucial detail is that the resulting number may contain leading zeroes. Since the result is interpreted as an integer, leading zeroes are automatically ignored. For example:

"0890" → 890

The input is a single integer num, where:

1 <= num <= 10^8

This tells us the number contains at most 9 digits, which is very small. Even a brute-force approach is feasible. However, the problem is classified as an easy greedy problem, which suggests there is a direct observation that allows us to compute the answer efficiently without checking every possibility.

Some important edge cases stand out immediately:

A number may already contain 9s everywhere, meaning the maximum value cannot increase.
A number may contain only one distinct digit, meaning remapping affects every position.
Replacing the leading digit with 0 can dramatically reduce the value because leading zeroes are allowed.
Numbers containing 0 already may behave differently when minimizing.
Single-digit numbers require careful handling because remapping can turn them into 0.

For example:

num = 9

Maximum:

9 → 9

Minimum:

9 → 0

Difference:

9 - 0 = 9

Approaches

Brute Force Approach

The most direct way to solve this problem is to try every possible remapping operation.

Since there are 10 possible source digits (0 to 9) and 10 possible target digits (0 to 9), we can test every pair (d1, d2).

For each pair:

Convert num into a string.
Replace every occurrence of digit d1 with digit d2.
Convert the result back into an integer.
Track the smallest and largest values encountered.

At the end, return:

max_value - min_value

This approach is correct because it explicitly evaluates every valid remapping and therefore cannot miss the optimal answer.

However, it performs unnecessary work. Even though the constraints are tiny, we are checking all 100 digit mappings when only a small number of meaningful remappings actually matter.

Key Insight for an Optimal Greedy Solution

To maximize the number, we want to make the most significant digits as large as possible.

The best strategy is:

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

Why does this work?

Digits on the left contribute more to the number than digits on the right. Therefore, the earliest opportunity to increase a digit gives the greatest gain. Replacing a later digit while ignoring an earlier improvable digit would always be suboptimal.

To minimize the number, we want to make the number as small as possible.

Since leading zeroes are allowed, the best strategy becomes:

Replace all occurrences of the first digit with 0

Why?

The first digit is the most significant. Turning it into 0 produces the greatest decrease possible. Since leading zeroes are allowed, there is no restriction preventing this.

For example:

Maximum:

1 → 9
99899

Minimum:

1 → 0
00890 → 890

Difference:

99899 - 890 = 99009

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(100 × d) = O(d)	O(d)	Try every digit remapping pair
Optimal	O(d)	O(d)	Greedily construct maximum and minimum

Here, d is the number of digits in num.

Algorithm Walkthrough

Convert num into a string so individual digits can be manipulated easily.
To compute the maximum value, scan the number from left to right and locate the first digit that is not '9'.

This digit represents the earliest opportunity to increase the number. Replacing all occurrences of this digit with '9' yields the greatest possible increase. 3. If every digit is already '9', the maximum remains unchanged. 4. To compute the minimum value, take the first digit of the number.

Since leading zeroes are allowed, replacing every occurrence of this digit with '0' produces the smallest possible number. 5. Convert both remapped strings back into integers. 6. Return:

maximum - minimum

Why it works

The algorithm relies on the positional significance of digits.

For the maximum value, changing a more significant digit always dominates changing a less significant digit. Therefore, the first digit that can be improved should always be upgraded to 9.

For the minimum value, reducing the leftmost digit gives the largest reduction because it contributes the greatest place value. Since leading zeroes are allowed, replacing the first digit with 0 is always optimal.

Because both choices are locally optimal at the most significant position, they are globally optimal.

Python Solution

class Solution:
    def minMaxDifference(self, num: int) -> int:
        num_str = str(num)

        # Compute maximum value
        max_str = num_str
        digit_to_replace = None

        for digit in num_str:
            if digit != '9':
                digit_to_replace = digit
                break

        if digit_to_replace is not None:
            max_str = num_str.replace(digit_to_replace, '9')

        # Compute minimum value
        min_str = num_str.replace(num_str[0], '0')

        return int(max_str) - int(min_str)

The implementation begins by converting the integer into a string, since digit replacement is easier with string operations.

To compute the maximum value, the code scans the digits from left to right looking for the first digit that is not '9'. Once found, all occurrences of that digit are replaced with '9'. If no such digit exists, the number already represents the largest possible arrangement.

For the minimum value, the implementation simply replaces every occurrence of the first digit with '0'. This works because the leftmost digit contributes the most to the overall number, and leading zeroes are permitted.

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

Go Solution

import "strconv"

func minMaxDifference(num int) int {
	numStr := strconv.Itoa(num)

	// Compute maximum value
	maxStr := numStr
	digitToReplace := byte(0)

	for i := 0; i < len(numStr); i++ {
		if numStr[i] != '9' {
			digitToReplace = numStr[i]
			break
		}
	}

	if digitToReplace != 0 {
		maxBytes := []byte(numStr)

		for i := 0; i < len(maxBytes); i++ {
			if maxBytes[i] == digitToReplace {
				maxBytes[i] = '9'
			}
		}

		maxStr = string(maxBytes)
	}

	// Compute minimum value
	firstDigit := numStr[0]
	minBytes := []byte(numStr)

	for i := 0; i < len(minBytes); i++ {
		if minBytes[i] == firstDigit {
			minBytes[i] = '0'
		}
	}

	maxVal, _ := strconv.Atoi(maxStr)
	minVal, _ := strconv.Atoi(string(minBytes))

	return maxVal - minVal
}

The Go solution follows the same greedy logic as the Python implementation. Since Go strings are immutable, we convert them into byte slices before performing in-place character replacement.

A sentinel value digitToReplace := byte(0) is used to indicate whether a non-9 digit was found for maximizing the number.

There are no integer overflow concerns because:

num <= 10^8

and all derived values remain well within Go's standard integer range.

Worked Examples

Example 1

num = 11891

Maximum Value Construction

Step	Current Digit	Action	Result
1	`1`	First non-9 found	Replace `1 → 9`
2	Entire number	Apply replacement	`99899`

Minimum Value Construction

Step	First Digit	Action	Result
1	`1`	Replace `1 → 0`	`00890`
2	Convert to integer	Leading zeroes removed	`890`

Final computation:

99899 - 890 = 99009

Output:

Example 2

num = 90

Maximum Value Construction

Step	Current Digit	Action	Result
1	`9`	Already optimal	Continue
2	`0`	First non-9 found	Replace `0 → 9`
3	Entire number	Apply replacement	`99`

Minimum Value Construction

Step	First Digit	Action	Result
1	`9`	Replace `9 → 0`	`00`
2	Convert to integer	Leading zeroes removed	`0`

Final computation:

99 - 0 = 99

Output:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(d)	At most a few linear scans through the digits
Space	O(d)	Strings created during replacement

The algorithm scans the digits a constant number of times. Since the number contains at most d digits, every operation is linear in the number length.

The extra memory comes from storing modified strings during remapping.

Test Cases

sol = Solution()

assert sol.minMaxDifference(11891) == 99009  # Example 1
assert sol.minMaxDifference(90) == 99  # Example 2

assert sol.minMaxDifference(1) == 9  # Single digit
assert sol.minMaxDifference(9) == 9  # Single digit already maxed
assert sol.minMaxDifference(99999) == 99999  # All digits are 9
assert sol.minMaxDifference(10000) == 90000  # Leading digit remapped to 0
assert sol.minMaxDifference(11111) == 99999  # All same digit
assert sol.minMaxDifference(12345) == 90000  # First digit affects both max and min
assert sol.minMaxDifference(90909) == 99999  # Mix of 9 and 0
assert sol.minMaxDifference(10) == 90  # Leading zero in minimum
assert sol.minMaxDifference(808) == 909  # Internal repeated digit
assert sol.minMaxDifference(100000000) == 900000000  # Upper constraint boundary

Test	Why
`11891`	Validates provided example with repeated digits
`90`	Validates provided example with leading zero result
`1`	Smallest possible input
`9`	Single digit already equal to 9
`99999`	Maximum cannot increase
`10000`	Leading digit replacement to zero
`11111`	All digits identical
`12345`	Distinct digits
`90909`	Mixed repeated digits
`10`	Minimum becomes zero
`808`	Non-leading repeated digit
`100000000`	Upper bound constraint

Edge Cases

One important edge case occurs when the number is already composed entirely of 9s.

For example:

A naive implementation might fail to find a digit to maximize and accidentally produce an invalid replacement. The implementation handles this by checking whether a non-9 digit exists before applying replacement. If none is found, the original number is preserved as the maximum.

Another tricky case involves leading zeroes after minimization.

For example:

Replacing the leading 1 with 0 gives:

Some implementations mistakenly treat this as an invalid transformation or preserve the leading digit. Since the problem explicitly allows leading zeroes, converting the string back to an integer correctly yields 0.

A third important edge case is when all digits are identical.

For example:

Both remapping operations affect every position. The maximum becomes:

and the minimum becomes:

The implementation correctly handles this because string replacement updates every occurrence of the selected digit globally.

Finally, single-digit numbers can easily introduce off-by-one errors.

For example:

The maximum becomes:

and the minimum becomes:

Because the algorithm treats the first digit uniformly regardless of length, no special-case handling is required.