Max Difference You Can Get From Changing an Integer solution and explanation
Google
9 more videos on this problem
Max Difference You Can Get From Changing an Integer | Made Easy | Leetcode 1432 | codestorywithMIKcodestorywithMIK · 20:13 · 7K views
Max Difference You Can Get From Changing an Integer | Leetcode 1432Techdose · 13:56 · 1K views
1432. Max Difference You Can Get From Changing an Integer (Leetcode Medium)Programming Live with Larry · 4:05 · 504 views
Max Difference You Can Get From Changing an Integer (Leetcode 1432)Coding Interviews · 28:12 · 502 views
1432. Max Difference You Can Get From Changing an Integer | Leetcode Daily - PythonLeetcode Daily · 6:16 · 337 views
1432 Max Difference You Can Get From Changing an Integer | LeetCode | GreedyR Sai Siddhu · 18:17 · 226 views
1432. Max Difference You Can Get From Changing an Integer | Greedy | Math | LeetcodeRapid Syntax · 14:46 · 203 views
Leetcode 1432. Max Difference You Can Get From Changing an Integer | Greedy String in PythonStatLearn Tech · 16:15 · 187 views
LeetCode 1432 | Max Difference You Can Get From Changing an Integer | Daily LeetCode 15th june, 2025LearnInDSA · 15:00 · 141 views
[English] 1432. Max Difference You Can Get From Changing an Integer [Leetcode Medium]Romain Lhotte · 13:43 · 82 views
The problem
You are given an integer num. You will apply the following steps exactly two times:
- Pick a digit
x (0 <= x <= 9). - Pick another digit
y (0 <= y <= 9). The digitycan be equal tox. - Replace all the occurrences of
xin the decimal representation ofnumbyy. - The new integer cannot have any leading zeros, also the new integer cannot be 0.
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 <= 108
Approach overview
Problem 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.
Approach 1: Maximize and Minimize by Digit Replacement
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.
def getMax(num):
s = list(str(num))
for i in range(len(s)):
if s[i] != '9':
digit = s[i]
s = ['9' if c == digit else c for c in s]
break
return int(''.join(s))
def getMin(num):
s = list(str(num))
digit = s[0]
replace = '1'
if s[0] == '1':
for i in range(1, len(s)):
if s[i] != '0' and s[i] != '1':
digit = s[i]
replace = '0'
break
s = [replace if c == digit else c for c in s]
return int(''.join(s))
def maxDifference(num):
a = getMax(num)
b = getMin(num)
return a - b
num = 555
print(maxDifference(num))public class MaxDifference {
public static int getMax(int num) {
char[] s = String.valueOf(num).toCharArray();
for (int i = 0; i < s.length; i++) {
if (s[i] != '9') {
char digit = s[i];
for (int j = 0; j < s.length; j++) {
if (s[j] == digit) {
s[j] = '9';
}
}
break;
}
}
return Integer.parseInt(new String(s));
}
public static int getMin(int num) {
char[] s = String.valueOf(num).toCharArray();
char digit = s[0];
char replace = '1';
if (s[0] == '1') {
for (int i = 1; i < s.length; i++) {
if (s[i] != '0' && s[i] != '1') {
digit = s[i];
replace = '0';
break;
}
}
}
for (int i = 0; i < s.length; i++) {
if (s[i] == digit) {
s[i] = replace;
}
}
return Integer.parseInt(new String(s));
}
public static int maxDifference(int num) {
int a = getMax(num);
int b = getMin(num);
return a - b;
}
public static void main(String[] args) {
int num = 555;
System.out.println(maxDifference(num));
}
}#include <iostream>
#include <string>
int getMax(int num) {
std::string s = std::to_string(num);
for (char &ch: s) {
if (ch != '9') {
char old_char = ch;
for (char &c: s) {
if (c == old_char) {
c = '9';
}
}
break;
}
}
return std::stoi(s);
}
int getMin(int num) {
std::string s = std::to_string(num);
char digit = s[0];
char replace = '1';
if (s[0] == '1') {
for (size_t i = 1; i < s.length(); ++i) {
if (s[i] != '0' && s[i] != '1') {
digit = s[i];
replace = '0';
break;
}
}
}
for (char &c: s) {
if (c == digit) {
c = replace;
}
}
return std::stoi(s);
}
int maxDifference(int num) {
int a = getMax(num);
int b = getMin(num);
return a - b;
}
int main() {
int num = 555;
std::cout << maxDifference(num) << std::endl;
return 0;
}function getMax(num) {
let s = num.toString().split('');
for (let i = 0; i < s.length; i++) {
if (s[i] !== '9') {
let digit = s[i];
s = s.map(c => (c === digit ? '9' : c));
break;
}
}
return parseInt(s.join(''), 10);
}
function getMin(num) {
let s = num.toString().split('');
let digit = s[0];
let replace = '1';
if (s[0] === '1') {
for (let i = 1; i < s.length; i++) {
if (s[i] !== '0' && s[i] !== '1') {
digit = s[i];
replace = '0';
break;
}
}
}
s = s.map(c => (c === digit ? replace : c));
return parseInt(s.join(''), 10);
}
function maxDifference(num) {
let a = getMax(num);
let b = getMin(num);
return a - b;
}
let num = 555;
console.log(maxDifference(num));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int getMax(int num) {
char s[10];
sprintf(s, "%d", num);
for (int i = 0; s[i]; i++) {
if (s[i] != '9') {
char digit = s[i];
for (int j = 0; s[j]; j++) {
if (s[j] == digit) {
s[j] = '9';
}
}
break;
}
}
return atoi(s);
}
int getMin(int num) {
char s[10];
sprintf(s, "%d", num);
char digit = s[0];
char replace = '1';
if (s[0] == '1') {
for (int i = 1; s[i]; i++) {
if (s[i] != '0' && s[i] != '1') {
digit = s[i];
break;
}
}
replace = '0';
}
for (int i = 0; s[i]; i++) {
if (s[i] == digit) {
s[i] = replace;
}
}
return atoi(s);
}
int maxDifference(int num) {
int a = getMax(num);
int b = getMin(num);
return a - b;
}
int main() {
int num = 555;
printf("%d\n", maxDifference(num));
return 0;
}using System;
class Program {
public static int GetMax(int num) {
char[] s = num.ToString().ToCharArray();
for (int i = 0; i < s.Length; i++) {
if (s[i] != '9') {
char digit = s[i];
for (int j = 0; j < s.Length; j++) {
if (s[j] == digit) {
s[j] = '9';
}
}
break;
}
}
return Int32.Parse(new string(s));
}
public static int GetMin(int num) {
char[] s = num.ToString().ToCharArray();
char digit = s[0];
char replace = '1';
if (s[0] == '1') {
for (int i = 1; i < s.Length; i++) {
if (s[i] != '0' && s[i] != '1') {
digit = s[i];
replace = '0';
break;
}
}
}
for (int i = 0; i < s.Length; i++) {
if (s[i] == digit) {
s[i] = replace;
}
}
return Int32.Parse(new string(s));
}
public static int MaxDifference(int num) {
int a = GetMax(num);
int b = GetMin(num);
return a - b;
}
public static void Main(string[] args) {
int num = 555;
Console.WriteLine(MaxDifference(num));
}
}The Python solution implements the logic using list and string transformations. The getMax function finds the first non-9 digit to replace, while the getMin function replaces the leading or first non-zero digit based on the conditions. The max difference is then calculated between the resulting numbers.
Time Complexity: O(n), where n is the number of digits in the number.
Space Complexity: O(n), considering the transformed list and string.
Approach 2: Alternative Simple Replacement Strategy
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.
def simpleMaxReplacement(num):
s = list(str(num))
for i in range(len(s)):
if s[i] != '9':
replacement = s[i]
s = ['9' if x == replacement else x for x in s]
break
return int(''.join(s))
def simpleMinReplacement(num):
s = list(str(num))
first_digit = s[0]
replacement = '1'
if first_digit == '1':
for i in range(1, len(s)):
if s[i] != '0' and s[i] != '1':
target = s[i]
s = ['0' if x == target else x for x in s]
break
elif first_digit != '0':
s = ['1' for _ in s]
return int(''.join(s))
def maxDifference(num):
return simpleMaxReplacement(num) - simpleMinReplacement(num)
print(maxDifference(555))public class SimpleMaxDifference {
static int simpleMaxReplacement(int num) {
char[] chars = String.valueOf(num).toCharArray();
for (int i = 0; i < chars.length; i++) {
if (chars[i] != '9') {
char target = chars[i];
for (int j = 0; j < chars.length; j++) {
if (chars[j] == target) chars[j] = '9';
}
break;
}
}
return Integer.parseInt(new String(chars));
}
static int simpleMinReplacement(int num) {
char[] chars = String.valueOf(num).toCharArray();
boolean changed = false;
if (chars[0] == '1') {
for (int i = 1; i < chars.length; i++) {
if (chars[i] != '0' && chars[i] != '1') {
char target = chars[i];
for (int j = 0; j < chars.length; j++) {
if (chars[j] == target) chars[j] = '0';
}
changed = true;
break;
}
}
}
if (!changed && chars[0] != '0') {
Arrays.fill(chars, '1');
}
return Integer.parseInt(new String(chars));
}
public static int maxDifference(int num) {
return simpleMaxReplacement(num) - simpleMinReplacement(num);
}
public static void main(String[] args) {
System.out.println(maxDifference(555));
}
}#include <iostream>
#include <string>
int simpleMaxReplacement(int num) {
std::string str = std::to_string(num);
for (char& c : str) {
if (c != '9') {
std::replace(str.begin(), str.end(), c, '9');
break;
}
}
return std::stoi(str);
}
int simpleMinReplacement(int num) {
std::string str = std::to_string(num);
bool replaced = false;
char replacement = '1';
if (str[0] == '1') {
for (char& c : str) {
if (c != '0' && c != '1') {
std::replace(str.begin(), str.end(), c, '0');
replaced = true;
break;
}
}
}
if (!replaced && str[0] != '0') {
std::replace(str.begin(), str.end(), str[0], replacement);
}
return std::stoi(str);
}
int maxDifference(int num) {
return simpleMaxReplacement(num) - simpleMinReplacement(num);
}
int main() {
int num = 555;
std::cout << maxDifference(num) << std::endl;
return 0;
}function simpleMaxReplacement(num) {
let s = num.toString().split('');
for (let i = 0; i < s.length; i++) {
if (s[i] !== '9') {
let replacement = s[i];
s = s.map(x => x === replacement ? '9' : x);
break;
}
}
return parseInt(s.join(''), 10);
}
function simpleMinReplacement(num) {
let s = num.toString().split('');
let firstDigit = s[0];
if (firstDigit === '1') {
for (let i = 1; i < s.length; i++) {
if (s[i] !== '0' && s[i] !== '1') {
let replacement = s[i];
s = s.map(x => x === replacement ? '0' : x);
break;
}
}
} else {
s = s.map(() => '1');
}
return parseInt(s.join(''), 10);
}
function maxDifference(num) {
let a = simpleMaxReplacement(num);
let b = simpleMinReplacement(num);
return a - b;
}
console.log(maxDifference(555));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int simpleMaxReplacement(int num) {
char s[10];
sprintf(s, "%d", num);
int length = strlen(s);
// Replace first non-9 digit with 9
for (int i = 0; i < length; i++) {
if (s[i] != '9') {
char org = s[i];
for (int j = 0; j < length; j++) {
if (s[j] == org) s[j] = '9';
}
break;
}
}
return atoi(s);
}
int simpleMinReplacement(int num) {
char s[10];
sprintf(s, "%d", num);
int length = strlen(s);
char digit = s[0];
// If first is '1' find first non-zero to '0'
if (s[0] == '1') {
for (int i = 1; i < length; i++) {
if (s[i] != '0' && s[i] != '1') {
digit = s[i];
for (int j = 0; j < length; j++) {
if (s[j] == digit) s[j] = '0';
}
break;
}
}
} else {
// Replace first digit with '1'
printf("Unable to replace first with a leading '1' otherwise");
}
return atoi(s);
}
int maxDifference(int num) {
int maxPossible = simpleMaxReplacement(num);
int minPossible = simpleMinReplacement(num);
return maxPossible - minPossible;
}
int main() {
int num = 555;
printf("%d\n", maxDifference(num));
return 0;
}using System;
using System.Linq;
public class Program {
public static int SimpleMaxReplacement(int num) {
char[] chars = num.ToString().ToCharArray();
for (int i = 0; i < chars.Length; i++) {
if (chars[i] != '9') {
char target = chars[i];
for (int j = 0; j < chars.Length; j++) {
if (chars[j] == target) chars[j] = '9';
}
break;
}
}
return int.Parse(new string(chars));
}
public static int SimpleMinReplacement(int num) {
char[] chars = num.ToString().ToCharArray();
bool changed = false;
if (chars[0] == '1') {
for (int i = 1; i < chars.Length; i++) {
if (chars[i] != '0' && chars[i] != '1') {
char target = chars[i];
for (int j = 0; j < chars.Length; j++) {
if (chars[j] == target) chars[j] = '0';
}
changed = true;
break;
}
}
}
if (!changed && chars[0] != '0') {
for (int i = 0; i < chars.Length; i++) {
chars[i] = '1';
}
}
return int.Parse(new string(chars));
}
public static int MaxDifference(int num) {
return SimpleMaxReplacement(num) - SimpleMinReplacement(num);
}
public static void Main() {
Console.WriteLine(MaxDifference(555));
}
}The Python implementation shifts focus on early possible identification for replacements involving 9 in maximum and 1 or 0 placement in minimum context. The code optimally uses list comprehensions to keep the transformations clean and manageable.
Time Complexity: O(n) where n is digit count.
Space Complexity: O(n) since list transformations involve new arrays.
Approach 3: Greedy
To obtain the maximum difference, we should take the maximum and minimum values, as this yields the largest difference.
Therefore, we first enumerate each digit in nums from high to low. If a digit is not 9, we replace all occurrences of that digit with 9 to obtain the maximum integer a.
Next, we enumerate each digit in nums from high to low again. The first digit cannot be 0, so if the first digit is not 1, we replace it with 1; for non-leading digits that are different from the first digit, we replace them with 0 to obtain the minimum integer b.
The answer is the difference a - b.
The time complexity is O(log num), and the space complexity is O(log num), where nums is the given integer.
function maxDiff(num: number): number {
let a = num.toString();
let b = a;
for (let i = 0; i < a.length; ++i) {
if (a[i] !== '9') {
a = a.split(a[i]).join('9');
break;
}
}
if (b[0] !== '1') {
b = b.split(b[0]).join('1');
} else {
for (let i = 1; i < b.length; ++i) {
if (b[i] !== '0' && b[i] !== '1') {
b = b.split(b[i]).join('0');
break;
}
}
}
return +a - +b;
}func maxDiff(num int) int {
a, b := num, num
s := strconv.Itoa(num)
for i := range s {
if s[i] != '9' {
a, _ = strconv.Atoi(strings.ReplaceAll(s, string(s[i]), "9"))
break
}
}
if s[0] > '1' {
b, _ = strconv.Atoi(strings.ReplaceAll(s, string(s[0]), "1"))
} else {
for i := 1; i < len(s); i++ {
if s[i] != '0' && s[i] != '1' {
b, _ = strconv.Atoi(strings.ReplaceAll(s, string(s[i]), "0"))
break
}
}
}
return a - b
}impl Solution {
pub fn max_diff(num: i32) -> i32 {
let a = num.to_string();
let mut a = a.clone();
let mut b = a.clone();
for c in a.chars() {
if c != '9' {
a = a.replace(c, "9");
break;
}
}
let chars: Vec<char> = b.chars().collect();
if chars[0] != '1' {
b = b.replace(chars[0], "1");
} else {
for &c in &chars[1..] {
if c != '0' && c != '1' {
b = b.replace(c, "0");
break;
}
}
}
a.parse::<i32>().unwrap() - b.parse::<i32>().unwrap()
}
}Complexity comparison
| 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) where n is digit count. |
| Greedy | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Max Difference You Can Get From Changing an Integer easy or hard?
The problem is rated Medium on LeetCode. The implementation is straightforward, but the challenge is recognizing the greedy rule for selecting which digit replacement produces the largest increase or decrease.
Max Difference You Can Get From Changing an Integer Python/Java solution
In Python or Java, convert the integer to a string, identify the digit to replace for maximizing and minimizing, perform the replacements using string operations, and convert the results back to integers. The overall complexity remains O(d).
How to solve Max Difference You Can Get From Changing an Integer in O(n)?
Treat the integer as a string and perform greedy digit replacement. For the maximum value, replace the first digit that is not 9 with 9 everywhere. For the minimum value, replace the first digit with 1 if possible, otherwise replace the first digit that is neither 0 nor 1 with 0. Both operations scan the digits once, giving O(n) time.
What is the best approach for Max Difference You Can Get From Changing an Integer?
The optimal solution uses a greedy digit replacement strategy. Convert the number to a string, replace the first non-9 digit with 9 to maximize the value, and replace digits carefully to minimize the value without introducing a leading zero. This approach runs in O(d) time where d is the number of digits.
Is Max Difference You Can Get From Changing an Integer asked at Google/Amazon/Meta?
Digit manipulation and greedy optimization problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of positional value and greedy reasoning rather than complex data structures.
What data structure is used in Max Difference You Can Get From Changing an Integer?
Most solutions convert the integer into a string or character array so digits can be replaced easily. The algorithm itself relies on greedy logic rather than advanced data structures.
What is the time complexity of Max Difference You Can Get From Changing an Integer?
The greedy solution runs in O(d) time and O(d) space, where d is the number of digits in the integer. Each pass scans the digits to determine which digit to replace for maximizing and minimizing the result.