LeetCode 2231 - Largest Number After Digit Swaps by Parity
The problem gives us a positive integer num and allows us to swap digits only if the two digits have the same parity. In
Difficulty: 🟢 Easy
Topics: Sorting, Heap (Priority Queue)
Solution
Problem Understanding
The problem gives us a positive integer num and allows us to swap digits only if the two digits have the same parity. In other words, an odd digit can only be swapped with another odd digit, and an even digit can only be swapped with another even digit.
The goal is to return the largest possible integer that can be formed after performing any number of valid swaps.
To understand the restriction more clearly, imagine the digits of the number are fixed into positions. At each position, the parity of the digit originally occupying that position effectively constrains what can go there. If a position originally contains an odd digit, only odd digits from other positions may replace it. Similarly, positions originally containing even digits can only ever contain even digits.
For example, in 1234, the odd digits are 1 and 3, while the even digits are 2 and 4. Since odd digits can freely swap among themselves, we can rearrange the odd digits in descending order (3,1). Likewise, the even digits can be rearranged in descending order (4,2). Reconstructing the number while preserving parity positions gives 3412, which is the maximum possible result.
The input consists of a single integer num, where 1 <= num <= 10^9. Since the upper bound is only one billion, the number contains at most 10 digits. This is a very small input size, meaning even moderately inefficient algorithms would likely pass. However, the problem is designed to test observation and greedy reasoning rather than raw performance.
There are several important edge cases to keep in mind. A number with only odd digits or only even digits should simply be sorted in descending order, since every digit can swap with every other digit. A single digit number should return unchanged because no swaps are possible. Numbers where parity alternates frequently can also be tricky because we cannot freely reorder the entire number, only digits within the same parity group.
Approaches
Brute Force Approach
A brute force solution would try every possible valid sequence of swaps and determine the largest number obtainable.
One way to think about this is as a graph search problem. Each number configuration becomes a state, and every valid parity swap produces another state. We could use a breadth first search or depth first search to explore all reachable numbers, keeping track of the maximum value encountered.
This approach is correct because it exhaustively explores every valid arrangement obtainable through parity preserving swaps. Since it considers all possibilities, it cannot miss the optimal answer.
However, this method is inefficient because the number of permutations grows factorially with the number of digits. Even though the digit count is small, generating and checking every reachable arrangement is unnecessary and computationally expensive.
Optimal Greedy Approach
The key observation is that parity positions are fixed.
Suppose a position originally contains an odd digit. Since we may only swap with other odd digits, that position can never contain an even digit. The same logic applies to even positions. Therefore, the only freedom we have is deciding which odd digit occupies an odd position and which even digit occupies an even position.
To maximize the resulting number, we should greedily place the largest available digit of the correct parity at every position, starting from the leftmost digit. Since earlier digits contribute more to the final numeric value, always choosing the largest valid digit locally also produces the globally optimal answer.
The algorithm works as follows:
- Extract all odd digits and all even digits.
- Sort both groups in descending order.
- Rebuild the number from left to right.
- For each original digit:
- If it was odd, place the largest remaining odd digit.
- If it was even, place the largest remaining even digit.
This guarantees the largest possible number.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n!) | O(n!) | Explores all valid parity-preserving permutations |
| Optimal | O(n log n) | O(n) | Sort odd and even digits independently, then reconstruct |
Algorithm Walkthrough
- Convert the integer into a string so that we can process individual digits easily.
- Traverse the digits and separate them into two groups based on parity. One list stores odd digits, and another stores even digits. We do this because digits may only swap within the same parity class.
- Sort both lists in descending order. This ensures that the largest remaining digit of each parity is always available first.
- Initialize two pointers, one for the odd list and one for the even list. These pointers track which digit should be used next.
- Iterate through the original digits from left to right. For each digit:
- If the digit is odd, append the largest unused odd digit.
- If the digit is even, append the largest unused even digit.
This greedy step works because digits placed earlier have greater positional significance in the final number. 6. Combine the chosen digits into a string and convert it back into an integer.
Why it works
The algorithm relies on the invariant that each position can only receive digits of the same parity as its original digit. Since parity positions are fixed, maximizing the number reduces to independently maximizing the digits assigned to odd and even slots.
At every position, choosing the largest available valid digit is optimal because earlier digits contribute more to the total value than later ones. Any smaller choice at a more significant position would necessarily produce a smaller overall number, regardless of future placements.
Python Solution
class Solution:
def largestInteger(self, num: int) -> int:
digits = list(str(num))
odd_digits = sorted(
[digit for digit in digits if int(digit) % 2 == 1],
reverse=True
)
even_digits = sorted(
[digit for digit in digits if int(digit) % 2 == 0],
reverse=True
)
odd_index = 0
even_index = 0
result = []
for digit in digits:
if int(digit) % 2 == 1:
result.append(odd_digits[odd_index])
odd_index += 1
else:
result.append(even_digits[even_index])
even_index += 1
return int("".join(result))
The implementation starts by converting the number into a list of digit characters, making iteration straightforward.
Next, it separates odd and even digits into two independent collections. Each collection is sorted in descending order so that the largest available digit is always accessible first.
The algorithm then iterates through the original digits. Instead of using the original digit, it replaces it with the largest remaining digit of the same parity. Two indices track how many digits from each sorted list have already been used.
Finally, the reconstructed digits are joined together and converted back into an integer.
Go Solution
import (
"sort"
"strconv"
)
func largestInteger(num int) int {
numStr := strconv.Itoa(num)
var oddDigits []int
var evenDigits []int
for _, ch := range numStr {
digit := int(ch - '0')
if digit%2 == 0 {
evenDigits = append(evenDigits, digit)
} else {
oddDigits = append(oddDigits, digit)
}
}
sort.Sort(sort.Reverse(sort.IntSlice(oddDigits)))
sort.Sort(sort.Reverse(sort.IntSlice(evenDigits)))
oddIndex := 0
evenIndex := 0
result := ""
for _, ch := range numStr {
digit := int(ch - '0')
if digit%2 == 0 {
result += strconv.Itoa(evenDigits[evenIndex])
evenIndex++
} else {
result += strconv.Itoa(oddDigits[oddIndex])
oddIndex++
}
}
answer, _ := strconv.Atoi(result)
return answer
}
The Go implementation follows the same logical structure as the Python version. Since Go does not have built in descending sort for slices, we use sort.Reverse(sort.IntSlice(...)).
Instead of storing digits as strings, Go stores them as integers. During reconstruction, strconv.Itoa() converts digits back into strings for concatenation.
Integer overflow is not a concern because the problem guarantees num <= 10^9, which easily fits inside Go's int type.
Worked Examples
Example 1
Input: num = 1234
First, separate digits by parity.
| Digit | Parity | Group |
|---|---|---|
| 1 | Odd | Odd list |
| 2 | Even | Even list |
| 3 | Odd | Odd list |
| 4 | Even | Even list |
After sorting:
| Group | Sorted Descending |
|---|---|
| Odd | [3, 1] |
| Even | [4, 2] |
Now reconstruct the number.
| Position | Original Digit | Required Parity | Chosen Digit | Result |
|---|---|---|---|---|
| 0 | 1 | Odd | 3 | 3 |
| 1 | 2 | Even | 4 | 34 |
| 2 | 3 | Odd | 1 | 341 |
| 3 | 4 | Even | 2 | 3412 |
Final answer: 3412
Example 2
Input: num = 65875
Separate digits by parity.
| Digit | Parity | Group |
|---|---|---|
| 6 | Even | Even list |
| 5 | Odd | Odd list |
| 8 | Even | Even list |
| 7 | Odd | Odd list |
| 5 | Odd | Odd list |
After sorting:
| Group | Sorted Descending |
|---|---|
| Odd | [7, 5, 5] |
| Even | [8, 6] |
Reconstruct the number.
| Position | Original Digit | Required Parity | Chosen Digit | Result |
|---|---|---|---|---|
| 0 | 6 | Even | 8 | 8 |
| 1 | 5 | Odd | 7 | 87 |
| 2 | 8 | Even | 6 | 876 |
| 3 | 7 | Odd | 5 | 8765 |
| 4 | 5 | Odd | 5 | 87655 |
Final answer: 87655
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log n) | Sorting odd and even digits dominates runtime |
| Space | O(n) | Extra storage for odd digits, even digits, and result |
The digit count is n, where n is the number of digits in num. We traverse the digits a constant number of times, which costs O(n). The expensive operation is sorting the odd and even groups. In the worst case, all digits belong to one group, making sorting cost O(n log n).
The extra space comes from storing separated digits and the reconstructed result, requiring O(n) memory.
Test Cases
solution = Solution()
assert solution.largestInteger(1234) == 3412 # Provided example 1
assert solution.largestInteger(65875) == 87655 # Provided example 2
assert solution.largestInteger(1) == 1 # Single digit
assert solution.largestInteger(2) == 2 # Single even digit
assert solution.largestInteger(13579) == 97531 # All odd digits
assert solution.largestInteger(86420) == 86420 # Already largest all-even
assert solution.largestInteger(2486) == 8642 # All even, reorder descending
assert solution.largestInteger(11111) == 11111 # Duplicate odd digits
assert solution.largestInteger(10203) == 30201 # Mixed parity with zeros
assert solution.largestInteger(247) == 427 # Cannot swap odd with even
assert solution.largestInteger(987654321) == 987654321 # Already optimal
assert solution.largestInteger(123456789) == 987654321 # Maximum rearrangement
| Test | Why |
|---|---|
1234 |
Validates provided example |
65875 |
Validates provided example with repeated odd digits |
1 |
Tests smallest possible input |
2 |
Tests single even digit |
13579 |
Verifies all odd digits can fully reorder |
86420 |
Confirms already optimal arrangement |
2486 |
Tests all even digits |
11111 |
Verifies duplicate handling |
10203 |
Ensures zeros are handled correctly |
247 |
Verifies parity restriction |
987654321 |
Already maximal arrangement |
123456789 |
Large mixed parity rearrangement |
Edge Cases
Single Digit Numbers
When num contains only one digit, no swaps are possible because there is nothing to exchange. A naive implementation might accidentally overcomplicate this case, but the algorithm naturally handles it. The odd or even list contains one element, and reconstruction simply reproduces the same digit.
Numbers With Only One Parity
If all digits are odd or all digits are even, every digit may swap with every other digit. In this situation, the optimal answer is simply the digits sorted in descending order. The implementation handles this automatically because one parity list becomes empty while the other contains all digits.
For example, 2486 becomes 8642, and 13579 becomes 97531.
Digits Containing Zero
Zero deserves special attention because it is an even digit. An incorrect implementation might treat it differently or accidentally move it into an odd slot.
For example, in 10203, the even digits are [0, 2, 0], and the odd digits are [1, 3]. Sorting and reconstructing by parity gives 30201, while preserving valid parity constraints. Since zero behaves like any other even digit, the implementation handles it correctly without requiring special logic.