LeetCode 670: Maximum Swap Solution in Python – A Step-by-Step Guide

What Is LeetCode 670: Maximum Swap?

In LeetCode 670: Maximum Swap, you’re given a non-negative integer num, and your task is to find the maximum possible value you can achieve by swapping at most one pair of digits in the number. Return this maximum value as an integer. For example, with num = 2736, swapping 2 and 7 yields 7236, the largest possible result. With num = 9973, swapping 9 and 7 gives 9973 (already max, no swap needed). The problem tests your ability to identify the optimal swap to maximize a number’s value efficiently.

Problem Statement

• Input:
• num: Non-negative integer.
• Output: An integer—maximum value after at most one swap.
• Rules:
• Swap at most one pair of digits.
• Use original digits only (permutation).
• Return largest possible number.

Constraints

• 0 ≤ num ≤ 10⁸.

Examples

• Input: num = 2736
• Output: 7236 (Swap 2 and 7)
• Input: num = 9973
• Output: 9973 (No swap needed)
• Input: num = 98368
• Output: 98863 (Swap 3 and 8)

These examples set the number—let’s solve it!

Understanding the Problem: Maximizing with a Swap

To solve LeetCode 670: Maximum Swap in Python, we need to find the maximum number achievable by swapping at most one pair of digits in num. A brute-force approach—trying all possible swaps and finding the max—would be O(n²), where n is the number of digits, reasonable for small numbers but inefficient for larger ones (up to 10⁸). Since we want the largest value, we can optimize by greedily seeking the best swap. We’ll use:

• Best Solution (Greedy with Digit Tracking): O(n) time, O(1) space—fast and clever.
• Alternative Solution (Brute-Force with Swaps): O(n²) time, O(n) space—simple but slower.

Let’s start with the greedy solution, breaking it down for beginners.

Best Solution: Greedy with Digit Tracking

Why This Is the Best Solution

The greedy with digit tracking approach is the top choice for LeetCode 670 because it’s efficient—O(n) time with O(1) space—and uses a smart strategy: track the last occurrence of each digit while scanning right-to-left, then find the first opportunity to swap with a larger digit to maximize the number. It fits constraints (num ≤ 10⁸, ~8 digits) perfectly and is intuitive once you see the tracking logic. It’s like scanning the number to spot the perfect swap in one go!

How It Works

Think of this as a digit spotter:

• Step 1: Convert to List:
• Turn num into a list of digits for easy manipulation.
• Step 2: Track Last Occurrences:
• Array last[0-9] stores the rightmost index of each digit.
• Scan right-to-left, update last[digit].
• Step 3: Find Swap:
• Scan left-to-right:
• For each digit, check if a larger digit exists to its right (in last).
• If found, swap and break (first swap maximizes).
• Step 4: Rebuild Number:
• Convert list back to integer.
• Step 5: Return Result:
• Return maximum number.

It’s like a swap seeker—track and trade!

Step-by-Step Example

Example: num = 2736

• Step 1: Digits = [2, 7, 3, 6].
• Step 2: Track last occurrences (right-to-left):
• i=3: last[6] = 3.
• i=2: last[3] = 2.
• i=1: last[7] = 1.
• i=0: last[2] = 0.
• last = [-1, -1, 0, 2, -1, -1, 3, 1, -1, -1].
• Step 3: Find swap (left-to-right):
• i=0: digit=2, check 3-9:
• last[7] = 1 > 0, swap 2 and 7: [7, 2, 3, 6], break.
• Step 4: Rebuild: 7236.
• Output: 7236.

Example: num = 9973

• Step 1: Digits = [9, 9, 7, 3].
• Step 2: Track:
• i=3: last[3] = 3.
• i=2: last[7] = 2.
• i=1: last[9] = 1.
• i=0: last[9] = 0.
• last = [-1, -1, -1, 3, -1, -1, -1, 2, -1, 0].
• Step 3: Find swap:
• i=0: 9, no larger digit, continue.
• i=1: 9, no larger digit, continue.
• i=2: 7, last[9] = 0 < 2, no swap, continue.
• No swap found.
• Step 4: Rebuild: 9973.
• Output: 9973.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def maximumSwap(self, num: int) -> int:
        # Step 1: Convert number to list of digits
        digits = list(str(num))
        n = len(digits)

        # Step 2: Track last occurrence of each digit
        last = [-1] * 10  # Index of last occurrence of digits 0-9
        for i in range(n):
            last[int(digits[i])] = i

        # Step 3: Find first swap opportunity
        for i in range(n):
            # Check digits larger than current
            for d in range(9, int(digits[i]), -1):
                if last[d] > i:
                    # Swap and return
                    digits[i], digits[last[d]] = digits[last[d]], digits[i]
                    return int(''.join(digits))

        # Step 4: No swap needed, return original
        return num

• Lines 4-6: Convert: Stringify num, get digits list.
• Lines 9-11: Track: Fill last with rightmost indices.
• Lines 14-20: Find swap:
• Scan left-to-right, check for larger digit to right, swap if found.
• Line 23: Return: Original if no swap.
• Time Complexity: O(n)—two passes over digits.
• Space Complexity: O(1)—fixed-size array (10).

This is like a digit maximizer—track and swap!

Alternative Solution: Brute-Force with Swaps

Why an Alternative Approach?

The brute-force with swaps approach tries all possible swaps—O(n²) time, O(n) space. It’s simpler conceptually, testing each pair and finding the max, but inefficient for larger numbers. It’s like trying every magic trick until you find the best one!

How It Works

Picture this as a swap tester:

• Step 1: Convert to list of digits.
• Step 2: Try all swaps:
• For each pair (i, j), swap, compute value, track max.
• Step 3: Return max value.

It’s like a trial swapper—test and pick!

Step-by-Step Example

Example: num = 2736

• Step 1: Digits = [2, 7, 3, 6].
• Step 2: Try swaps:
• (0, 1): [7, 2, 3, 6] = 7236, max = 7236.
• (0, 2): [3, 7, 2, 6] = 3726, max = 7236.
• (0, 3): [6, 7, 3, 2] = 6732, max = 7236.
• (1, 2): [2, 3, 7, 6] = 2376, max = 7236.
• (1, 3): [2, 6, 3, 7] = 2637, max = 7236.
• (2, 3): [2, 7, 6, 3] = 2763, max = 7236.
• Step 3: Return 7236.
• Output: 7236.

Code for Brute-Force Approach

Copy codeclass Solution:
    def maximumSwap(self, num: int) -> int:
        # Step 1: Convert to list of digits
        digits = list(str(num))
        n = len(digits)
        max_num = num

        # Step 2: Try all possible swaps
        for i in range(n):
            for j in range(i + 1, n):
                # Swap digits
                digits[i], digits[j] = digits[j], digits[i]
                curr_num = int(''.join(digits))
                max_num = max(max_num, curr_num)
                # Restore digits
                digits[i], digits[j] = digits[j], digits[i]

        # Step 3: Return maximum number
        return max_num

• Lines 4-6: Convert: Digits list, init max.
• Lines 9-15: Try swaps:
• Swap each pair, compute value, update max, restore.
• Line 18: Return max_num.
• Time Complexity: O(n²)—n² swaps, O(n) conversion each.
• Space Complexity: O(n)—digits list.

It’s a swap explorer—try and maximize!

Comparing the Two Solutions

• Greedy (Best):
• Pros: O(n) time, O(1) space, fast and elegant.
• Cons: Tracking logic less obvious.
• Brute-Force (Alternative):
• Pros: O(n²) time, O(n) space, straightforward.
• Cons: Slower, less efficient.

Greedy wins for speed.

Additional Examples and Edge Cases

• Input: num = 1234
• Output: 4231 (Swap 1 and 4).
• Input: num = 0
• Output: 0 (No swap possible).

Greedy handles these well.

Complexity Breakdown

• Greedy: Time O(n), Space O(1).
• Brute-Force: Time O(n²), Space O(n).

Greedy is optimal.

Key Takeaways

• Greedy: Digit tracking—smart!
• Brute-Force: Swap testing—clear!
• Swaps: Maximizing is fun.
• Python Tip: Arrays rock—see Python Basics.

Final Thoughts: Maximize That Number

LeetCode 670: Maximum Swap in Python is a fun number challenge. Greedy with digit tracking offers efficiency and elegance, while brute-force provides a clear baseline. Want more? Try LeetCode 283: Move Zeroes or LeetCode 561: Array Partition. Ready to swap? Head to Solve LeetCode 670 on LeetCode and maximize that number today!