How do you solve Maximum Swap on LeetCode?

Maximum Swap (LeetCode #670) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Swapping should always aim for the largest possible digit to the left.

What is the brute force solution for Maximum Swap?

The brute force approach for Maximum Swap is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves generating all possible numbers by swapping every pair of digits in the given number. This allows us to check which swap yields the maximum value, but it can be inefficient due to the number of combinations. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Maximum Swap?

Maximum Swap uses the following concepts: Math, Greedy. The recommended patterns to study are: Greedy, Array.

What are the interview tips for Maximum Swap?

Always clarify if multiple swaps are allowed or just one. Discuss your thought process and approach before jumping into coding. Consider edge cases like single-digit numbers or already maximum numbers.

What are common mistakes when solving Maximum Swap?

Not considering the case where no swap is needed. Failing to swap back in the brute force approach, leading to incorrect results.

#670

Maximum Swap

Medium

MathGreedyGreedyArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution leverages the idea of tracking the last occurrence of each digit and finding the best swap that maximizes the number. This approach is efficient because it only requires a single pass to identify the best swap.

⚙️

Algorithm

4 steps

1Step 1: Convert the number to a string to access digits easily.
2Step 2: Create an array to store the last occurrence index of each digit (0-9).
3Step 3: Iterate through the digits from left to right, checking if a larger digit exists later in the number that can be swapped.
4Step 4: If a larger digit is found, perform the swap and return the new number immediately.

solution.py11 lines

1# Full working Python code
2
3def maximumSwap(num):
4    num_str = list(str(num))
5    last = {int(x): i for i, x in enumerate(num_str)}
6    for i in range(len(num_str)):
7        for d in range(9, int(num_str[i]), -1):
8            if last.get(d, -1) > i:
9                num_str[i], num_str[last[d]] = num_str[last[d]], num_str[i]
10                return int(''.join(num_str))
11    return num

ℹ

Complexity note: The time complexity is O(n) because we only make a few passes through the digits of the number. The space complexity is O(1) since we are using a fixed-size array to store the last indices of digits.

1Swapping should always aim for the largest possible digit to the left.
2Tracking the last occurrence of each digit helps in efficiently finding the best swap.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.