#2231

Easy

auto_awesomeSorting plus Heap (Priority Queue)

LeetCode Problem Workspace

Largest Number After Digit Swaps by Parity

Maximize a number by swapping digits of the same parity using sorting and priority queue techniques efficiently.

Problem Statement

You are given a positive integer num. You may swap any two digits of num that have the same parity, meaning both digits are odd or both are even. Your goal is to maximize num by performing any number of such swaps.

Return the largest possible value of num after these swaps. For example, if num = 1234, swapping odd digits and even digits appropriately results in 3412, which is the maximal number achievable under these constraints.

Examples

Example 1

Input: num = 1234

Output: 3412

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

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

Solution Approach

Separate digits by parity

Split the digits of num into two lists: one for odd digits and one for even digits. This enables independent reordering of each parity group without violating the swap rules.

Sort each parity group descending

Sort the odd digits in descending order and the even digits in descending order. Larger digits should be positioned earlier to maximize the overall number value, aligning with the problem pattern of sorting plus heap usage.

Reconstruct the number

Iterate through the original number's digit positions. Replace each odd digit with the next largest odd from the sorted list and each even digit with the next largest even. This guarantees the largest number achievable using parity swaps.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) due to sorting the parity groups, and space complexity is O(n) to store the separate digit lists. Heap-based reconstruction can maintain similar bounds but allows easy retrieval of largest available digits per parity.

What Interviewers Usually Probe

The candidate quickly separates digits by parity and explains why swaps are limited by parity.
They prioritize placing larger digits in higher positions to maximize value.
They recognize sorting plus heap structure as the key pattern to efficiently compute the solution.

Common Pitfalls or Variants

Common pitfalls

Swapping digits without considering parity, which violates problem constraints.
Reversing digits incorrectly or using ascending order instead of descending order, resulting in suboptimal number.
Using in-place swaps without tracking positions, leading to misplacement of largest digits in the reconstruction step.

Follow-up variants

Allow only a fixed number of swaps instead of unlimited swaps.
Extend to negative numbers, requiring careful handling of sign during swaps.
Compute the k-th largest number achievable using parity swaps.

FAQ

What is the key pattern to solve Largest Number After Digit Swaps by Parity?

The key pattern is sorting plus heap. Separating digits by parity and using a heap ensures the largest available digit is placed first.

Can digits of different parity be swapped?

No, swaps are restricted to digits of the same parity only. Mixing parities violates the problem constraints.

Why sort digits in descending order?

Sorting descending ensures the largest digits occupy the highest value positions, maximizing the resulting number.

What data structures are helpful for this problem?

Lists for parity groups and a heap or priority queue are effective to efficiently pick the largest available digit per parity.

What is the time complexity of the optimal approach?

Sorting the parity groups takes O(n log n) time and reconstructing the number is O(n), so overall time complexity is O(n log n).

terminal

Solution

Solution 1: Counting

We can use an array $\textit{cnt}$ of length $10$ to count the occurrences of each digit in the integer $\textit{num}$. We also use an index array $\textit{idx}$ to record the largest available even and odd digits, initially set to $[8, 9]$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def largestInteger(self, num: int) -> int:
        nums = [int(c) for c in str(num)]
        cnt = Counter(nums)
        idx = [8, 9]
        ans = 0
        for x in nums:
            while cnt[idx[x & 1]] == 0:
                idx[x & 1] -= 2
            ans = ans * 10 + idx[x & 1]
            cnt[idx[x & 1]] -= 1
        return ans

Solution 2

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def largestInteger(self, num: int) -> int:
        nums = [int(c) for c in str(num)]
        cnt = Counter(nums)
        idx = [8, 9]
        ans = 0
        for x in nums:
            while cnt[idx[x & 1]] == 0:
                idx[x & 1] -= 2
            ans = ans * 10 + idx[x & 1]
            cnt[idx[x & 1]] -= 1
        return ans

Continue Practicing

#2285 maximum total importance of roads #2146 k highest ranked items within a price range #2333 minimum sum of squared difference