Largest Number After Digit Swaps by Parity

Difficulty: Easy | Acceptance: 65.30% | Paid: No Topics: Sorting, Heap (Priority Queue)

You are given a positive integer num. You may swap two digits if they have the same parity (both odd digits or both even digits). Return the largest integer you can get after any number of swaps.

Table of Contents

• Examples
• Constraints
• Sorting by Parity
• Using Priority Queues
• Brute Force Swapping

Examples

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 <= 10^9

Sorting by Parity

Intuition Since we can swap any two digits of the same parity, we can independently rearrange all even digits among even positions and all odd digits among odd positions. To maximize the number, we should place the largest even digits in the leftmost even positions and the largest odd digits in the leftmost odd positions.

Steps

• Convert the number to a string to process each digit
• Separate even and odd digits into two separate lists
• Sort both lists in descending order
• Reconstruct the result by picking from the appropriate sorted list based on the original digit’s parity

class Solution:
    def largestInteger(self, num: int) -> int:
        s = str(num)
        evens = []
        odds = []
        
        for c in s:
            digit = int(c)
            if digit % 2 == 0:
                evens.append(digit)
            else:
                odds.append(digit)
        
        evens.sort(reverse=True)
        odds.sort(reverse=True)
        
        result = []
        even_idx = 0
        odd_idx = 0
        
        for c in s:
            digit = int(c)
            if digit % 2 == 0:
                result.append(str(evens[even_idx]))
                even_idx += 1
            else:
                result.append(str(odds[odd_idx]))
                odd_idx += 1
        
        return int(''.join(result))

Complexity

• Time: O(n log n) where n is the number of digits
• Space: O(n) for storing the digit lists
• Notes: This is the most straightforward approach with clean implementation

Using Priority Queues

Intuition Instead of sorting all digits at once, we can use max heaps (priority queues) to efficiently retrieve the largest available digit of the required parity as we reconstruct the number from left to right.

Steps

• Create two max heaps, one for even digits and one for odd digits
• Push all digits into their respective heaps (using negative values for max heap in languages with min-heap only)
• Iterate through the original number and for each position, pop the largest digit from the appropriate heap

import heapq

class Solution:
    def largestInteger(self, num: int) -> int:
        s = str(num)
        evens = []
        odds = []
        
        for c in s:
            digit = int(c)
            if digit % 2 == 0:
                heapq.heappush(evens, -digit)
            else:
                heapq.heappush(odds, -digit)
        
        result = []
        for c in s:
            digit = int(c)
            if digit % 2 == 0:
                result.append(str(-heapq.heappop(evens)))
            else:
                result.append(str(-heapq.heappop(odds)))
        
        return int(''.join(result))

Complexity

• Time: O(n log n) where n is the number of digits
• Space: O(n) for the heaps
• Notes: Useful when you need to process digits in a specific order without sorting everything upfront

Brute Force Swapping

Intuition We can simulate the swapping process by repeatedly comparing and swapping adjacent digits of the same parity. This is similar to bubble sort where we only allow swaps between digits with matching parity.

Steps

• Convert the number to a character array
• Use nested loops to compare each pair of digits
• If two digits have the same parity and swapping them would increase the number, swap them
• Continue until no more beneficial swaps are possible

class Solution:
    def largestInteger(self, num: int) -> int:
        s = list(str(num))
        n = len(s)
        
        for i in range(n):
            for j in range(i + 1, n):
                if (int(s[i]) % 2) == (int(s[j]) % 2):
                    if s[i] < s[j]:
                        s[i], s[j] = s[j], s[i]
        
        return int(''.join(s))

Complexity

• Time: O(n²) where n is the number of digits
• Space: O(n) for the character array
• Notes: Simple to understand but less efficient; useful for educational purposes or when n is very small