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
- Scanning from the left, the first position where a larger digit appears later is the one worth improving.
- 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).
- Precompute the rightmost occurrence of each digit 0-9, then scan left to right looking for any larger digit that occurs later.
- 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
numhas 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.