What is the time complexity of LeetCode 1432. Max Difference You Can Get From Changing an Integer?

The Python solution on this page runs in O(\log \textit{num}).

What is the space complexity of LeetCode 1432. Max Difference You Can Get From Changing an Integer?

The Python solution on this page uses O(\log \textit{num}), where \textit{nums} is the given integer auxiliary space.

Max Difference You Can Get From Changing an Integer — LeetCode 1432 Python Solution

MediumGreedyMath

Problem: #1432
Pattern: Greedy
Reading time: 3 min
Source: leetcode.com

The problem

You are given an integer num. You will apply the following steps to num two separate times: Pick a digit x (0 <= x <= 9).

Example

Input: num = 555
Output: 888
Explanation: The first time pick x = 5 and y = 9 and store the new integer in a.

Python solution

Python

class Solution:
    def maxDiff(self, num: int) -> int:
        a, b = str(num), str(num)
        for c in a:
            if c != "9":
                a = a.replace(c, "9")
                break
        if b[0] != "1":
            b = b.replace(b[0], "1")
        else:
            for c in b[1:]:
                if c not in "01":
                    b = b.replace(c, "0")
                    break
        return int(a) - int(b)

Complexity

Measure	Complexity
Time	O(\log \textit{num})
Space	O(\log \textit{num}), where \textit{nums} is the given integer auxiliary

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 1432. Max Difference You Can Get From Changing an Integer is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1432. Max Difference You Can Get From Changing an Integer?: LeetCode 1432. Max Difference You Can Get From Changing an Integer is rated Medium on LeetCode.
What is the time complexity of LeetCode 1432. Max Difference You Can Get From Changing an Integer?: The Python solution on this page runs in O(\log \textit{num}).
What is the space complexity of LeetCode 1432. Max Difference You Can Get From Changing an Integer?: The Python solution on this page uses O(\log \textit{num}), where \textit{nums} is the given integer auxiliary space.
What topics does LeetCode 1432. Max Difference You Can Get From Changing an Integer cover?: LeetCode 1432. Max Difference You Can Get From Changing an Integer is tagged Greedy and Math on LeetCode.