Skip to main content
Talentd

Largest Number After Digit Swaps by Parity - Solution & Explanation

EasySortingHeap (Priority Queue)15 min readAsked at: IBM, Salesforce, Zscaler +2
Practice this problem

Problem Statement

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 <= 109

Approach Overview

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.

Approach 1: Sort Parity Groups

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Priority Queue (Heap) Utilization

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.

Code

C++Python

C++

Python

Complexity

Time Complexity: O(n log n) due to heap operations.
Space Complexity: O(n) for the heaps storing the digits.

Try this approach in the editor →

Approach 3: Counting

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sort Parity Groups

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.

Priority Queue (Heap) Utilization

Time Complexity: O(n log n) due to heap operations.
Space Complexity: O(n) for the heaps storing the digits.

Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sort Parity GroupsO(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.

Video Solution

Largest Number After Digit Swaps by Parity | Leetcode 2231 | Max Heaps | Contest 288 🔥🔥 • Coding Decoded • 3,375 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Largest Number After Digit Swaps by Parity easy or hard?
Largest Number After Digit Swaps by Parity is classified as an Easy problem. The key idea is recognizing that digits can be freely rearranged within their parity group, allowing a greedy solution using sorting or heaps.
Largest Number After Digit Swaps by Parity Python/Java solution
In Python or Java, extract digits from the number, place odd digits and even digits into separate lists, sort them in descending order, and rebuild the number by selecting from the appropriate list based on the original digit's parity. This approach runs in O(n log n) time and O(n) space.
How to solve Largest Number After Digit Swaps by Parity in O(n)?
Since digits range only from 0–9, a counting approach can reduce sorting overhead by storing frequency counts for odd and even digits. Rebuilding the number by always selecting the largest available digit from the correct parity group can achieve near O(n) time. Most implementations, however, use sorting for simplicity.
What is the best approach for Largest Number After Digit Swaps by Parity?
The most common solution separates digits into odd and even groups, sorts both groups in descending order, and reconstructs the number using the largest available digit of the same parity. This greedy strategy guarantees the maximum possible number. The time complexity is O(n log n) due to sorting.
Is Largest Number After Digit Swaps by Parity asked at Google/Amazon/Meta?
Parity-based digit manipulation and greedy rearrangement problems frequently appear in coding interviews at large tech companies. Variants of digit reordering and constraint-based swaps are common practice questions for companies like Google, Amazon, and Meta.
What data structure is used in Largest Number After Digit Swaps by Parity?
The common implementation uses arrays or lists to store odd and even digits, followed by sorting. Another valid approach uses a max-heap (priority queue) to always retrieve the largest available digit of the required parity.
What is the time complexity of Largest Number After Digit Swaps by Parity?
The typical solution runs in O(n log n) time because the odd and even digit groups are sorted before reconstruction. Extracting digits and rebuilding the result takes O(n). Space complexity is O(n) to store the parity groups.

Ready to solve this problem?

Practice Largest Number After Digit Swaps by Parity with our built-in code editor and test cases.

Practice on FleetCode
Previous

Largest Number At Least Twice of Others

Next

Rearrange Array Elements by Sign