Maximum Difference by Remapping a Digit solution and explanation
Google
9 more videos on this problem
Maximum Difference by Remapping a Digit | Easy | 2 Ways | Leetcode 2566 | codestorywithMIKcodestorywithMIK · 26:45 · 5K views
Maximum Difference by Remapping a Digit || Leetcode-2566 || C++Aryan Mittal · 6:23 · 1K views
A. Maximum Difference by Remapping a Digit - LEETCODE BIWEEKLY CONTEST 98 (Detailed Logic explained)Joyjit Codes · 3:23 · 469 views
2566. Maximum Difference by Remapping a Digit | Greedy | LeetcodeRapid Syntax · 7:18 · 407 views
2566. Maximum Difference by Remapping a Digit | Leetcode Daily - PythonLeetcode Daily · 5:02 · 371 views
2566. Maximum Difference by Remapping a Digit - Bi-Weekly Contest 98 (Explanation + Code)Sourin Majumdar · 8:58 · 323 views
Maximum Difference by Remapping a Digit | Leetcode 2566 | Biweekly 98Tech Courses · 5:31 · 204 views
2566. Maximum Difference by Remapping a Digit (Leetcode Easy)Programming Live with Larry · 4:23 · 178 views
2566 Maximum Difference by Remapping a Digit | LeetCode | GreedyR Sai Siddhu · 15:16 · 147 views
Maximum Difference by Remapping a Digit | LeetCode 2566 | Greedy | Java Code | Developer CoderDeveloper Coder · 7:34 · 143 views
The problem
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.
def maxDiff(num: int) -> int:
num_str = str(num)
max_num, min_num = num_str, num_str
for d in num_str:
if d != '9':
max_num = num_str.replace(d, '9')
break
for d in num_str:
if d != '0':
min_num = num_str.replace(d, '0')
if min_num[0] == '0':
min_num = min_num.replace('0', d) # To prevent leading zero issue.
break
return int(max_num) - int(min_num)
print(maxDiff(11891)) # Output: 99009public class Main {
public static int maxDiff(int num) {
String numStr = String.valueOf(num);
char[] maxNumArr = numStr.toCharArray();
char[] minNumArr = numStr.toCharArray();
// Find max number
for (int i = 0; i < maxNumArr.length; i++) {
if (maxNumArr[i] != '9') {
char temp = maxNumArr[i];
for (int j = 0; j < maxNumArr.length; j++) {
if (maxNumArr[j] == temp) {
maxNumArr[j] = '9';
}
}
break;
}
}
// Find min number
for (int i = 0; i < minNumArr.length; i++) {
if (minNumArr[i] != '0') {
char temp = minNumArr[i];
for (int j = 0; j < minNumArr.length; j++) {
if (minNumArr[j] == temp) {
minNumArr[j] = '0';
}
}
if(minNumArr[0] == '0') {
break;
}
break;
}
}
int maxNum = Integer.parseInt(new String(maxNumArr));
int minNum = Integer.parseInt(new String(minNumArr));
return maxNum - minNum;
}
public static void main(String[] args) {
System.out.println(maxDiff(11891)); // Output: 99009
}
}function maxDiff(num) {
let numStr = num.toString();
let maxNum = numStr;
let minNum = numStr;
for (let i = 0; i < numStr.length; i++) {
if (maxNum[i] !== '9') {
maxNum = maxNum.replace(new RegExp(maxNum[i], 'g'), '9');
break;
}
}
for (let i = 0; i < numStr.length; i++) {
if (minNum[i] !== '0') {
minNum = minNum.replace(new RegExp(minNum[i], 'g'), '0');
if (minNum[0] === '0') {
minNum = minNum.replace('0', minNum[i]);
}
break;
}
}
return parseInt(maxNum) - parseInt(minNum);
}
console.log(maxDiff(11891)); // Output: 99009#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int maxDiff(int num) {
char num_str[10];
sprintf(num_str, "%d", num);
int len = strlen(num_str);
char max_num[10], min_num[10];
strcpy(max_num, num_str);
strcpy(min_num, num_str);
// Get max number
for (int i = 0; i < len; i++) {
if (max_num[i] != '9') {
for (int j = 0; j < len; j++) {
if (max_num[j] == max_num[i]) {
max_num[j] = '9';
}
}
break;
}
}
// Get min number
for (int i = 0; i < len; i++) {
if (min_num[i] != '0') {
for (int j = 0; j < len; j++) {
if (min_num[j] == min_num[i]) {
min_num[j] = '0';
}
}
if(min_num[0] == '0') {
min_num[0] = min_num[i];
}
break;
}
}
return atoi(max_num) - atoi(min_num);
}
int main() {
printf("%d\n", maxDiff(11891)); // Output: 99009
return 0;
}using System;
public class Solution {
public static int MaxDiff(int num) {
char[] numStr = num.ToString().ToCharArray();
char[] maxNum = (char[])numStr.Clone();
char[] minNum = (char[])numStr.Clone();
for (int i = 0; i < numStr.Length; i++) {
if (maxNum[i] != '9') {
char temp = maxNum[i];
for (int j = 0; j < maxNum.Length; j++) {
if (maxNum[j] == temp) {
maxNum[j] = '9';
}
}
break;
}
}
for (int i = 0; i < numStr.Length; i++) {
if (minNum[i] != '0' || i == 0) {
char temp = minNum[i];
for (int j = 0; j < minNum.Length; j++) {
if (minNum[j] == temp) {
minNum[j] = '0';
}
}
break;
}
}
int maxNumber = int.Parse(new string(maxNum));
int minNumber = int.Parse(new string(minNum));
return maxNumber - minNumber;
}
public static void Main() {
Console.WriteLine(MaxDiff(11891)); // Output: 99009
}
}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.
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.
def maxDiff(num: int) -> int:
num_str = str(num)
max_num = num_str
min_num = num_str
# Create max number
if '9' in num_str:
for char in num_str:
if char != '9':
max_num = num_str.replace(char, '9')
break
else:
max_num = num_str
# Create min number
head = num_str[0]
if head == '1':
for char in num_str[1:]:
if char != '0':
min_num = num_str.replace(char, '0')
break
else:
min_num = num_str.replace(head, '1') # Avoid leading zero issue by replacing the leading digit
return int(max_num) - int(min_num)
print(maxDiff(11891)) # Output: 99009public class Main {
public static int maxDiff(int num) {
String numStr = String.valueOf(num);
char[] maxNumArr = numStr.toCharArray();
char[] minNumArr = numStr.toCharArray();
// For max number, replace first non-'9' digit
for (int i = 0; i < maxNumArr.length; i++) {
if (maxNumArr[i] != '9') {
char temp = maxNumArr[i];
for (int j = 0; j < maxNumArr.length; j++) {
if (maxNumArr[j] == temp) {
maxNumArr[j] = '9';
}
}
break;
}
}
// For min number, choose strategies according to first digit
if (minNumArr[0] != '1') {
char first = minNumArr[0];
for (int j = 0; j < minNumArr.length; j++) {
if (minNumArr[j] == first) {
minNumArr[j] = '1';
}
}
} else {
for (int i = 1; i < minNumArr.length; i++) {
if (minNumArr[i] != '0' && minNumArr[i] != '1') {
char temp = minNumArr[i];
for (int j = i; j < minNumArr.length; j++) {
if (minNumArr[j] == temp) {
minNumArr[j] = '0';
}
}
break;
}
}
}
int maxNum = Integer.parseInt(new String(maxNumArr));
int minNum = Integer.parseInt(new String(minNumArr));
return maxNum - minNum;
}
public static void main(String[] args) {
System.out.println(maxDiff(11891)); // Output: 99009
}
}function maxDiff(num) {
let numStr = num.toString();
let maxNum, minNum;
if (numStr.includes('9')) {
maxNum = numStr;
for (let i = 0; i < numStr.length; i++) {
if (maxNum[i] !== '9') {
maxNum = maxNum.replace(new RegExp(maxNum[i], 'g'), '9');
break;
}
}
} else {
maxNum = numStr.replace(/[0-8]/, '9');
}
if (numStr[0] === '1') {
minNum = numStr;
for (let i = 1; i < numStr.length; i++) {
if (minNum[i] !== '0') {
minNum = minNum.replace(new RegExp(minNum[i], 'g'), '0');
break;
}
}
} else {
minNum = numStr.replace(numStr[0], '1');
}
return parseInt(maxNum) - parseInt(minNum);
}
console.log(maxDiff(11891));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int maxDiff(int num) {
char num_str[10];
sprintf(num_str, "%d", num);
int len = strlen(num_str);
char max_num[10], min_num[10];
strcpy(max_num, num_str);
strcpy(min_num, num_str);
// Calculate max number
for (int i = 0; i < len; i++) {
if (max_num[i] != '9') {
for (int j = 0; j < len; j++) {
if (max_num[j] == num_str[i]) {
max_num[j] = '9';
}
}
break;
}
}
// Calculate min number
if (min_num[0] != '1') {
for (int j = 0; j < len; j++) {
if (min_num[j] == min_num[0]) {
min_num[j] = '1';
}
}
} else {
for (int i = 1; i < len; i++) {
if (min_num[i] != '0' && min_num[i] != '1') {
for (int j = i; j < len; j++) {
if (min_num[j] == min_num[i]) {
min_num[j] = '0';
}
}
break;
}
}
}
return atoi(max_num) - atoi(min_num);
}
int main() {
printf("%d\n", maxDiff(11891)); // Output: 99009
return 0;
}using System;
public class Solution {
public static int MaxDiff(int num) {
char[] numArray = num.ToString().ToCharArray();
char[] maxArray = new char[numArray.Length];
char[] minArray = new char[numArray.Length];
Array.Copy(numArray, maxArray, numArray.Length);
Array.Copy(numArray, minArray, numArray.Length);
// Max number logic
for (int i = 0; i < maxArray.Length; i++) {
if (maxArray[i] != '9') {
char digit = maxArray[i];
for (int j = 0; j < maxArray.Length; j++) {
if (maxArray[j] == digit) {
maxArray[j] = '9';
}
}
break;
}
}
// Min number logic
if (minArray[0] != '1') {
var digit = minArray[0];
for (int j = 0; j < minArray.Length; j++) {
if (minArray[j] == digit) {
minArray[j] = '1';
}
}
} else {
for (int i = 1; i < minArray.Length; i++) {
if (minArray[i] != '0' && minArray[i] != '1') {
var digit = minArray[i];
for (int j = i; j < minArray.Length; j++) {
if (minArray[j] == digit) {
minArray[j] = '0';
}
}
break;
}
}
}
return Int32.Parse(new string(maxArray)) - Int32.Parse(new string(minArray));
}
public static void Main() {
Console.WriteLine(MaxDiff(11891));
}
}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.
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.
class Solution {
public:
int minMaxDifference(int num) {
string s = to_string(num);
string t = s;
char first = s[0];
for (char& c : s) {
if (c == first) {
c = '0';
}
}
int mi = stoi(s);
for (int i = 0; i < t.size(); ++i) {
if (t[i] != '9') {
char second = t[i];
for (int j = i; j < t.size(); ++j) {
if (t[j] == second) {
t[j] = '9';
}
}
return stoi(t) - mi;
}
}
return num - mi;
}
};function minMaxDifference(num: number): number {
const s = num.toString();
const mi = +s.replaceAll(s[0], '0');
for (const c of s) {
if (c !== '9') {
const mx = +s.replaceAll(c, '9');
return mx - mi;
}
}
return num - mi;
}func minMaxDifference(num int) int {
s := []byte(strconv.Itoa(num))
first := s[0]
for i := range s {
if s[i] == first {
s[i] = '0'
}
}
mi, _ := strconv.Atoi(string(s))
t := []byte(strconv.Itoa(num))
for i := range t {
if t[i] != '9' {
second := t[i]
for j := i; j < len(t); j++ {
if t[j] == second {
t[j] = '9'
}
}
mx, _ := strconv.Atoi(string(t))
return mx - mi
}
}
return num - mi
}impl Solution {
pub fn min_max_difference(num: i32) -> i32 {
let s = num.to_string();
let mi = s.replace(s.chars().next().unwrap(), "0").parse::<i32>().unwrap();
for c in s.chars() {
if c != '9' {
let mx = s.replace(c, "9").parse::<i32>().unwrap();
return mx - mi;
}
}
num - mi
}
}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 | – |
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 |
Frequently asked questions
Is Maximum Difference by Remapping a Digit easy or hard?
LeetCode classifies this problem as Easy. The logic relies on recognizing that the most significant digit has the largest impact on the value, so the greedy choice of which digit to replace immediately leads to the optimal answer.
How to solve Maximum Difference by Remapping a Digit in O(n)?
Treat the digits greedily based on place value. Scan the number from left to right to find the first digit eligible for replacement. Replace it with 9 to build the maximum value. For the minimum value, replace the first digit with 1 if possible, otherwise replace the first non 0/1 digit with 0. Each digit is processed once, giving O(n) time where n is the number of digits.
What is the best approach for Maximum Difference by Remapping a Digit?
The optimal approach uses a greedy digit-remapping strategy. For the maximum number, replace the first digit that is not 9 with 9 everywhere. For the minimum number, replace the first digit with 1 if it is not already 1; otherwise replace the first digit that is neither 0 nor 1 with 0. This produces the optimal result in O(d) time where d is the number of digits.
What data structure is used in Maximum Difference by Remapping a Digit?
The solution mainly relies on string or digit array manipulation rather than complex data structures. Converting the integer into a string allows easy scanning and replacement of digits while applying greedy rules.
What is the time complexity of Maximum Difference by Remapping a Digit?
The time complexity is O(d) because the algorithm scans the digits of the number a constant number of times. The space complexity ranges from O(d) when using strings to build the new numbers to O(1) with a single-pass optimized implementation.
Maximum Difference by Remapping a Digit Python or Java solution approach?
Both Python and Java implementations follow the same greedy rule. Convert the number to a string, determine which digit should be replaced for the maximum and minimum values, perform the replacements, and compute the difference. The implementation runs in O(d) time.
Is Maximum Difference by Remapping a Digit asked at Google or Amazon interviews?
Greedy digit manipulation problems similar to this appear in interviews at companies like Google, Amazon, and Meta. The exact problem may not always appear, but the concept of maximizing or minimizing numbers through digit operations is a common interview pattern.