⚡Flashcard Drill➔
NeetCode #819LC-670MediumGreedy
← Back to All Problems

#819 · #670 · Maximum Swap(最大交换)

📌 Problem Statement & Constraints

You are given an integer num. You may swap two digits at most once to get the maximum valued number. Return the maximum value you can get. Constraints: 0 <= num <= 10^8.

💡 Core Algorithmic Approaches

  1. Scanning from the left, the first position where a larger digit appears later is the one worth improving.
  2. To maximise, that position should take the largest digit available to its right, and among ties the rightmost occurrence (so the smaller digit lands as far right as possible).
  3. Precompute the rightmost occurrence of each digit 0-9, then scan left to right looking for any larger digit that occurs later.
  4. Swap and return; if no such pair exists the number is already maximal.

💻 Benchmark Python3 Implementation

class Solution:
    def maximumSwap(self, num: int) -> int:
        s = list(str(num))
        last = {int(d): i for i, d in enumerate(s)}   # rightmost occurrence of each digit
        for i, ch in enumerate(s):
            for big in range(9, int(ch), -1):
                if last.get(big, -1) > i:
                    j = last[big]
                    s[i], s[j] = s[j], s[i]
                    return int("".join(s))
        return num

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): the digit count is at most 9 and the inner loop is bounded by 10.
💾 Space Complexity
O(1): a 10-entry dictionary and the digit list.

⚠️ Interview Pitfalls & Follow-ups

  • Picking the leftmost occurrence of the largest digit: the rightmost occurrence keeps the swapped-out digit as far right as possible, which is optimal.
  • Scanning the largest digit globally first: you must fix the leftmost improvable position first, otherwise the swap wastes the highest place value.
  • Swapping equal digits: the search range is range(9, int(ch), -1), so equal digits are excluded and the result is unchanged when no larger digit exists.
  • Assuming num has at least two digits: for a single-digit number the loop finds nothing and returns the number unchanged.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems