You are given an integer num. You will apply the following steps exactly two times:
x (0 <= x <= 9).y (0 <= y <= 9). The digit y can be equal to x.x in the decimal representation of num by y.Let a and b be the results of applying the operations to num the first and second times, respectively.
Return the max difference between a and b.
Example 1:
Input: num = 555 Output: 888 Explanation: The first time pick x = 5 and y = 9 and store the new integer in a. The second time pick x = 5 and y = 1 and store the new integer in b. We have now a = 999 and b = 111 and max difference = 888
Example 2:
Input: num = 9 Output: 8 Explanation: The first time pick x = 9 and y = 9 and store the new integer in a. The second time pick x = 9 and y = 1 and store the new integer in b. We have now a = 9 and b = 1 and max difference = 8
Constraints:
1 <= num <= 108Problem Overview: Given an integer num, you can pick a digit x and replace every occurrence of it with another digit y. Perform the operation twice: once to maximize the value and once to minimize it. Return the difference between the two results.
Approach 1: Maximize and Minimize by Digit Replacement (Greedy) (Time: O(d), Space: O(d))
Treat the number as a string so you can manipulate individual digits. To maximize the value, scan from left to right and find the first digit that is not 9. Replace every occurrence of that digit with 9. This produces the largest possible number because the most significant non‑9 digit contributes the biggest increase when upgraded.
To minimize the value, avoid creating a leading zero. If the first digit is not 1, replace all occurrences of that digit with 1. If the first digit is already 1, scan for the first digit that is neither 0 nor 1 and replace all its occurrences with 0. This keeps the number valid while pushing the value down as much as possible.
The greedy insight: changes on the most significant digits dominate the final value. By modifying the earliest eligible digit, you maximize the effect of a single global replacement. This solution only scans the digits a few times, so the runtime is linear in the number of digits d. The logic is a classic example of greedy decision making applied to a math manipulation problem.
Approach 2: Alternative Simple Replacement Strategy (Time: O(100d), Space: O(d))
A straightforward strategy tries all valid replacement pairs. Choose a digit x from 0–9 and a replacement digit y from 0–9. Replace every occurrence of x in the number and compute the resulting integer. Skip results that introduce a leading zero. Track the maximum and minimum values produced.
There are at most 100 digit pairs, and each transformation scans the number once, so the time complexity is O(100d), effectively linear for typical constraints. This method is simple to implement and easy to reason about because it brute‑forces every allowed transformation.
Recommended for interviews: The greedy digit replacement approach. It demonstrates that you understand how positional value in numbers affects optimization decisions. Brute force works and shows correctness, but the greedy method proves you can reason about digit significance and reduce the search space efficiently.
To achieve the maximum difference between two numbers obtained by replacing digits, we should try to make one number as large as possible and the other as small as possible. The first operation should replace the highest possible digit with 9s to maximize the number, while the second operation should replace the first non-zero digit with 1 to minimize the number.
The solution involves creating two helper functions: getMax and getMin. The getMax function replaces the first non-9 digit in the integer with 9s to maximize it. The getMin function replaces the first non-zero digit with 1 (or 0 for non-leading digits) to minimize the number. Finally, the difference between these two transformed numbers is returned.
Time Complexity: O(n), where n is the number of digits in the number.
Space Complexity: O(n) for the character array used to manipulate the digits.
This approach focuses on an alternative systematic strategy for choosing x and y based on simplicity and effectiveness. The main aim is to put more effort on understanding edge cases and trivial replacements rather than directly targeting all possible replacements.
This approach uses simple maximum and minimum replacements as building block logic that focuses on quick target assignments. It also takes into account the prevention of unpleasant replacements like leading zeroes.
Time Complexity: O(n) for character iteration.
Space Complexity: O(n) due to storage requirements for transformation.
| Approach | Complexity |
|---|---|
| Maximize and Minimize by Digit Replacement | Time Complexity: O(n), where n is the number of digits in the number. |
| Alternative Simple Replacement Strategy | Time Complexity: O(n) for character iteration. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Max/Min Digit Replacement | O(d) | O(d) | Best general solution. Efficient and expected in coding interviews. |
| Enumerate All Digit Replacement Pairs | O(100d) | O(d) | Useful for quick implementation or verifying greedy logic. |
Max Difference You Can Get From Changing an Integer | Made Easy | Leetcode 1432 | codestorywithMIK • codestorywithMIK • 7,013 views views
Watch 9 more video solutions →Practice Max Difference You Can Get From Changing an Integer with our built-in code editor and test cases.
Practice on FleetCode