Maximum Swap Python Solution with Tests

Tested Python solution for LeetCode 670 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 670, Medium. Topics: Math, Greedy. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 18 parametrized pytest cases, and a playground notebook:

lcpy gen -n 670   # by problem number
lcpy gen -s maximum_swap   # by problem name

​

Problem

You are given an integer num. You can swap two digits at most once to get the maximum valued number.

Return the maximum valued number you can get.

​

Examples

Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Input: num = 9973
Output: 9973
Explanation: No swap.

​

Constraints

• 0 <= num <= 10^8

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(d) where d is the number of digits
    # Space: O(d)
    def maximum_swap(self, num: int) -> int:
        digits = list(str(num))
        last: dict[int, int] = {int(d): i for i, d in enumerate(digits)}
        for i, d in enumerate(digits):
            for bigger in range(9, int(d), -1):
                if bigger in last and last[bigger] > i:
                    j = last[bigger]
                    digits[i], digits[j] = digits[j], digits[i]
                    return int("".join(digits))
        return num

​

Complexity

Time	Space
O(d) where d is the number of digits	O(d)

​

Tags

NeetCode All.