Skip to main content
Talentd

Max Difference You Can Get From Changing an Integer - Solution & Explanation

MediumMathGreedy23 min readAsked at: Amazon, Meta, Google +3
Practice this problem

Problem Statement

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 digit y can be equal to x.
  • Replace all the occurrences of x in the decimal representation of num by y.
  • 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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) for character iteration.
Space Complexity: O(n) due to storage requirements for transformation.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Maximize and Minimize by Digit Replacement

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.

Alternative Simple Replacement Strategy

Time Complexity: O(n) for character iteration.
Space Complexity: O(n) due to storage requirements for transformation.

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Max/Min Digit ReplacementO(d)O(d)Best general solution. Efficient and expected in coding interviews.
Enumerate All Digit Replacement PairsO(100d)O(d)Useful for quick implementation or verifying greedy logic.

Video Solution

Max Difference You Can Get From Changing an Integer | Made Easy | Leetcode 1432 | codestorywithMIK • codestorywithMIK • 7,305 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Max Difference You Can Get From Changing an Integer with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer