You are given a positive integer num. You may swap any two digits of num that have the same parity (i.e. both odd digits or both even digits).
Return the largest possible value of num after any number of swaps.
Example 1:
Input: num = 1234 Output: 3412 Explanation: Swap the digit 3 with the digit 1, this results in the number 3214. Swap the digit 2 with the digit 4, this results in the number 3412. Note that there may be other sequences of swaps but it can be shown that 3412 is the largest possible number. Also note that we may not swap the digit 4 with the digit 1 since they are of different parities.
Example 2:
Input: num = 65875 Output: 87655 Explanation: Swap the digit 8 with the digit 6, this results in the number 85675. Swap the first digit 5 with the digit 7, this results in the number 87655. Note that there may be other sequences of swaps but it can be shown that 87655 is the largest possible number.
Constraints:
1 <= num <= 109Problem Overview: You are given an integer num. You may swap digits only with other digits that have the same parity (odd with odd, even with even). The goal is to rearrange the digits so the resulting number is as large as possible while respecting this restriction.
The constraint that swaps must preserve parity means each digit position can only receive digits from the same parity group. Odd digits can move only among odd positions, and even digits only among even positions. The problem reduces to reorganizing two independent groups of digits.
Approach 1: Sort Parity Groups (O(n log n) time, O(n) space)
Extract all digits from the number while keeping track of their parity. Store odd digits in one list and even digits in another. Sort both lists in descending order so the largest digits are used first. Then iterate through the original digit positions again: if the current digit position originally held an even digit, place the largest remaining even digit from the sorted list; if it held an odd digit, place the largest remaining odd digit.
The key insight is that swaps within the same parity group allow complete reordering inside that group. Sorting each group guarantees the largest available digit fills the leftmost valid position, which maximizes the final number. This approach is straightforward and performs well for typical integer lengths. It relies on basic sorting operations.
Approach 2: Priority Queue (Heap) Utilization (O(n log n) time, O(n) space)
Instead of sorting upfront, push odd digits and even digits into separate max-heaps. A max-heap ensures the largest available digit is always accessible in O(log n) time. After building the heaps, iterate through the digits of the original number. For each position, check the parity and pop the largest digit from the corresponding heap.
This approach produces the same result as sorting but retrieves the next best digit dynamically. Heaps are useful when the problem requires repeatedly extracting the maximum element during reconstruction. Implementation typically uses a priority queue, which guarantees efficient insertion and removal.
Recommended for interviews: The sorted parity groups approach is the most common and easiest to explain. It clearly demonstrates understanding of parity constraints and greedy placement of digits. The heap approach shows familiarity with priority queues and is a solid alternative when repeated maximum extraction is required. Showing the sorting approach first proves correctness quickly, while mentioning the heap variant demonstrates broader data structure knowledge.
This approach involves separating digits based on parity (odd and even). Once separated, each group is sorted in descending order. The digits from these sorted lists are then re-assigned to their original positions.
The C solution converts the integer to a string to process each digit. It segregates odd and even digits, sorts each group in descending order, then reconstructs the number by placing sorted digits back in their original parity positions.
Time Complexity: O(n log n) due to sorting, where n is the number of digits.
Space Complexity: O(n) for the storage of digits.
This approach utilizes priority queues (heaps) to efficiently sort and retrieve the largest elements of each parity group. This guarantees that when re-constructing the number from sorted parts, the retrieval operations are optimal.
In C++, the standard priority_queue is used for maintaining a max-heap property. This helps in efficiently sorting and accessing the largest elements while maintaining a structured and clear approach.
Time Complexity: O(n log n) due to heap operations.
Space Complexity: O(n) for the heaps storing the digits.
We can use an array cnt of length 10 to count the occurrences of each digit in the integer num. We also use an index array idx to record the largest available even and odd digits, initially set to [8, 9].
Next, we traverse each digit of the integer num. If the digit is odd, we take the digit corresponding to index 1 in idx; otherwise, we take the digit corresponding to index 0. If the count of the digit is 0, we decrement the digit by 2 and continue checking until we find a digit that meets the condition. Then, we update the answer and the count of the digit, and continue traversing until we have processed all digits of the integer num.
The time complexity is O(log num), and the space complexity is O(log num).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sort Parity Groups | Time Complexity: O(n log n) due to sorting, where n is the number of digits. |
| Priority Queue (Heap) Utilization | Time Complexity: O(n log n) due to heap operations. |
| Counting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort Parity Groups | O(n log n) | O(n) | Best general solution. Simple implementation using sorting and greedy reconstruction. |
| Priority Queue (Heap) | O(n log n) | O(n) | Useful when repeatedly extracting the largest element dynamically or demonstrating heap usage. |
Largest Number After Digit Swaps by Parity | Leetcode 2231 | Max Heaps | Contest 288 🔥🔥 • Coding Decoded • 3,312 views views
Watch 9 more video solutions →Practice Largest Number After Digit Swaps by Parity with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor