Largest Number After Digit Swaps by Parity - Video Solutions

Problem 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.