Maximum Difference by Remapping a Digit - Solution & Explanation
Problem Statement
You are given an integer num. You know that Bob will sneakily remap one of the 10 possible digits (0 to 9) to another digit.
Return the difference between the maximum and minimum values Bob can make by remapping exactly one digit in num.
Notes:
- When Bob remaps a digit d1 to another digit d2, Bob replaces all occurrences of
d1innumwithd2. - Bob can remap a digit to itself, in which case
numdoes not change. - Bob can remap different digits for obtaining minimum and maximum values respectively.
- The resulting number after remapping can contain leading zeroes.
Example 1:
Input: num = 11891 Output: 99009 Explanation: To achieve the maximum value, Bob can remap the digit 1 to the digit 9 to yield 99899. To achieve the minimum value, Bob can remap the digit 1 to the digit 0, yielding 890. The difference between these two numbers is 99009.
Example 2:
Input: num = 90 Output: 99 Explanation: The maximum value that can be returned by the function is 99 (if 0 is replaced by 9) and the minimum value that can be returned by the function is 0 (if 9 is replaced by 0). Thus, we return 99.
Constraints:
1 <= num <= 108
Approach Overview
Problem Overview: You receive an integer num. You can choose a digit x and remap every occurrence of it to another digit y. Perform this operation separately to produce a maximum value and a minimum value, then return the difference between them.
Approach 1: Digit-by-Digit Remapping (O(d) time, O(d) space)
Convert the number into a string so each digit is easy to inspect and modify. To build the maximum number, scan from left to right and locate the first digit that is not 9. Replace all occurrences of that digit with 9. This greedy step maximizes the most significant positions first.
For the minimum number, treat the leading digit differently to avoid creating a leading zero. If the first digit is not 1, replace all occurrences of that digit with 1. Otherwise, scan for the first digit that is neither 0 nor 1 and replace all of its occurrences with 0. The algorithm processes each digit at most once, giving O(d) time and O(d) space for the transformed strings.
This approach clearly separates the logic for maximum and minimum construction, which makes it easy to reason about during interviews.
Approach 2: Single Pass Optimized Remapping (O(d) time, O(1) space)
The greedy idea can be implemented while scanning the digits only once. Track the candidate digit for the maximum transformation (first non-9) and the candidate digit for the minimum transformation based on the leading-digit rule. As you iterate, build the resulting numbers by applying the chosen remapping rules on the fly.
The key insight is that the digit selected for replacement never changes once chosen. The most significant position dominates the final value, so the first eligible digit determines the mapping. This reduces extra passes and avoids building intermediate arrays. Time complexity remains O(d) while auxiliary space becomes O(1) aside from the output integers.
The strategy relies on greedy digit selection and simple arithmetic operations. Problems like this often appear under greedy and math categories because the optimal decision is made locally at the highest place value.
Recommended for interviews: The greedy remapping logic is what interviewers expect. Start with the digit-by-digit construction to explain the reasoning clearly. Then mention the single-pass optimization to show you recognize that only the first eligible digit determines the transformation.
Approach 1: Digit-by-Digit Remapping Approach
This approach involves iterating through each digit of the number. You need to determine which single digit change would lead to the greatest possible increase in the number (for the max value) and which single digit change would lead to the greatest possible decrease (for the min value). To find the max value, you should try remapping the first non-nine digit to nine. For the min value, try remapping the first non-zero digit to zero, keeping in mind about not creating a leading zero. Calculate the max and min numbers and derive the result by computing the difference between them.
This Python solution first converts the number to a string. We iterate through each digit to find a suitable candidate for remapping to achieve the maximum number by making the smallest digit to '9'. Similarly, another loop replaces the smallest digit with '0' while checking for the leading zero case for the minimum number.
Code
Python
C
Java
C#
JavaScript
Complexity
Time Complexity: O(n), where n is the number of digits in the number. Space Complexity: O(n), due to string operations.
Approach 2: Single Pass Optimized Remapping Approach
In this optimized approach, we try to minimize the iterations by directly determining the first target digit which is to be changed in order to generate either the largest possible number or the smallest possible number in one single sweep through the digit array. This process minimizes redundant checks and iterations by working based on the first impactful change alone.
This second Python solution optimizes by immediately remapping the first encounter to maximize values strategically and minimizes redundant calculations. It directly yields the most impactful change.
Code
Python
C
Java
C#
JavaScript
Complexity
Time Complexity: O(n), where n is the number of digits. Space Complexity: O(n), due to string operations.
Approach 3: Greedy
First, we convert the number to a string s.
To get the minimum value, we just need to find the first digit s[0] in the string s, and then replace all s[0] in the string with 0.
To get the maximum value, we need to find the first digit s[i] in the string s that is not 9, and then replace all s[i] in the string with 9.
Finally, return the difference between the maximum and minimum values.
The time complexity is O(log n), and the space complexity is O(log n). Where n is the size of the number num.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C
Complexity Comparison
| Approach | Complexity |
|---|---|
| Digit-by-Digit Remapping Approach | Time Complexity: O(n), where n is the number of digits in the number. Space Complexity: O(n), due to string operations. |
| Single Pass Optimized Remapping Approach | Time Complexity: O(n), where n is the number of digits. Space Complexity: O(n), due to string operations. |
| Greedy | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Digit-by-Digit Remapping | O(d) | O(d) | Best for readability and interviews when explaining greedy digit replacement |
| Single Pass Optimized Remapping | O(d) | O(1) | When minimizing extra memory and combining max/min construction in one traversal |
Video Solution
Maximum Difference by Remapping a Digit | Easy | 2 Ways | Leetcode 2566 | codestorywithMIK • codestorywithMIK • 5,567 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Difference by Remapping a Digit easy or hard?
How to solve Maximum Difference by Remapping a Digit in O(n)?
What is the best approach for Maximum Difference by Remapping a Digit?
What data structure is used in Maximum Difference by Remapping a Digit?
What is the time complexity of Maximum Difference by Remapping a Digit?
Maximum Difference by Remapping a Digit Python or Java solution approach?
Is Maximum Difference by Remapping a Digit asked at Google or Amazon interviews?
Ready to solve this problem?
Practice Maximum Difference by Remapping a Digit with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor