Problem Description

You are given a positive integer num. You can swap any two digits in the number as long as both digits have the same parity - meaning both digits must be odd (1, 3, 5, 7, 9) or both must be even (0, 2, 4, 6, 8).

For example, in the number 1234, you could swap the 1 and 3 (both odd), or swap the 2 and 4 (both even), but you cannot swap 1 and 2 (different parity).

You can perform any number of such swaps. Your goal is to find the largest possible value of num after performing these swaps optimally.

The key insight is that since you can only swap digits of the same parity, the positions of odd and even digits are fixed - an odd digit position will always contain an odd digit, and an even digit position will always contain an even digit. To maximize the number, you want to place the largest available digits of the appropriate parity in the leftmost positions.

Intuition

Since we can only swap digits with the same parity, each position in the number is "locked" to either odd or even digits. For instance, if position 0 has an odd digit, it will always contain an odd digit after any valid swaps.

To maximize the final number, we want to place the largest possible digit at each position, starting from the leftmost (most significant) position. The constraint is that we must use a digit with the correct parity for that position.

Think of it this way: we have two separate pools of digits - one for odd digits and one for even digits. As we build our answer from left to right, at each position we need to pick the largest available digit from the appropriate pool based on what parity that position requires.

This leads us to a greedy approach:

1. Count all available digits in the original number (both odd and even)
2. For each position from left to right, check what parity is needed (based on the original digit at that position)
3. Pick the largest available digit with that parity
4. Use that digit and decrease its count

The solution uses cnt to track available digits and idx = [8, 9] to track the current largest even and odd digits we're looking for. The expression x & 1 cleverly determines parity (returns 0 for even, 1 for odd). When we run out of a particular digit, we move to the next smaller digit of the same parity by decrementing by 2 (since digits of the same parity differ by 2).

Learn more about Sorting and Heap (Priority Queue) patterns.

Solution Approach

The solution uses a counting approach with a greedy strategy to build the largest possible number.

Data Structures Used:

• Convert the number to a list of digits: nums = [int(c) for c in str(num)]
• Use Counter to count occurrences of each digit: cnt = Counter(nums)
• Maintain an index array idx = [8, 9] where:
  • idx[0] tracks the current largest even digit to check
  • idx[1] tracks the current largest odd digit to check

Algorithm Steps:

1. Initialize tracking variables:

   • ans = 0 to build the result number
   • idx[0] = 8 (start checking from largest even digit)
   • idx[1] = 9 (start checking from largest odd digit)

2. Process each digit position from left to right: For each digit x in the original number:

   a. Determine parity: Use x & 1 to get:

   • 0 if x is even
   • 1 if x is odd

   b. Find the largest available digit with matching parity:

   while cnt[idx[x & 1]] == 0:
       idx[x & 1] -= 2

   This loop decrements by 2 to stay within the same parity (e.g., 9→7→5→3→1 for odd, 8→6→4→2→0 for even)

   c. Build the answer:

   • Multiply current answer by 10 and add the selected digit: ans = ans * 10 + idx[x & 1]
   • Decrease the count of used digit: cnt[idx[x & 1]] -= 1

3. Return the final answer

Example Walkthrough: For num = 1234:

• Digits: [1, 2, 3, 4], counts: {1:1, 2:1, 3:1, 4:1}
• Position 0 (odd): Pick largest odd digit = 3
• Position 1 (even): Pick largest even digit = 4
• Position 2 (odd): Pick remaining odd digit = 1
• Position 3 (even): Pick remaining even digit = 2
• Result: 3412

The time complexity is O(n) where n is the number of digits, and space complexity is O(1) since we only store counts for at most 10 digits.

Example Walkthrough

Let's walk through the solution with num = 52841:

Step 1: Initialize

• Convert to digits: nums = [5, 2, 8, 4, 1]
• Count occurrences: cnt = {5:1, 2:1, 8:1, 4:1, 1:1}
• Set idx = [8, 9] (largest even and odd digits to check)
• ans = 0

Step 2: Process each position

Position 0 (digit 5, odd):

• Parity check: 5 & 1 = 1 (odd)
• Look for largest odd digit: idx[1] = 9
• Check cnt[9] = 0, so decrement: idx[1] = 7
• Check cnt[7] = 0, so decrement: idx[1] = 5
• Check cnt[5] = 1 ✓ Found!
• Use digit 5: ans = 0 * 10 + 5 = 5
• Update: cnt[5] = 0

Position 1 (digit 2, even):

• Parity check: 2 & 1 = 0 (even)
• Look for largest even digit: idx[0] = 8
• Check cnt[8] = 1 ✓ Found!
• Use digit 8: ans = 5 * 10 + 8 = 58
• Update: cnt[8] = 0

Position 2 (digit 8, even):

• Parity check: 8 & 1 = 0 (even)
• Current idx[0] = 8, but cnt[8] = 0
• Decrement: idx[0] = 6, check cnt[6] = 0
• Decrement: idx[0] = 4, check cnt[4] = 1 ✓ Found!
• Use digit 4: ans = 58 * 10 + 4 = 584
• Update: cnt[4] = 0

Position 3 (digit 4, even):

• Parity check: 4 & 1 = 0 (even)
• Current idx[0] = 4, but cnt[4] = 0
• Decrement: idx[0] = 2, check cnt[2] = 1 ✓ Found!
• Use digit 2: ans = 584 * 10 + 2 = 5842
• Update: cnt[2] = 0

Position 4 (digit 1, odd):

• Parity check: 1 & 1 = 1 (odd)
• Current idx[1] = 5, but cnt[5] = 0
• Decrement: idx[1] = 3, check cnt[3] = 0
• Decrement: idx[1] = 1, check cnt[1] = 1 ✓ Found!
• Use digit 1: ans = 5842 * 10 + 1 = 58421
• Update: cnt[1] = 0

Result: 58421

Notice how odd positions (0, 4) kept odd digits (5, 1) and even positions (1, 2, 3) kept even digits (8, 4, 2), but we rearranged them optimally within their parity groups to maximize the number.

Solution Implementation

Time and Space Complexity

The time complexity is O(log num), where num is the input integer. This is because:

• Converting the integer to a string takes O(log num) time (the number of digits in num is proportional to log num)
• Creating the list of digits takes O(log num) time
• Building the Counter takes O(log num) time since there are at most O(log num) digits
• The main loop iterates through each digit once, which is O(log num) iterations
• Inside the loop, the while loop can decrement idx[x & 1] at most 5 times (for even digits: 8, 6, 4, 2, 0; for odd digits: 9, 7, 5, 3, 1), making it O(1) per iteration
• Therefore, the overall time complexity is O(log num)

The space complexity is O(log num) because:

• The nums list stores all digits of the input number, requiring O(log num) space
• The Counter dictionary stores at most 10 unique digits (0-9), which is O(1), but contains O(log num) total counts
• The idx array uses O(1) space
• The total space complexity is dominated by the storage of digits, resulting in O(log num)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Not Preserving Position-Based Parity Constraint

The Problem: A common mistake is to simply sort all odd and even digits separately and try to arrange them in descending order without respecting the original positions. For example, with num = 2143, you might incorrectly think you can rearrange it as 4321 by sorting all digits in descending order.

Why It's Wrong: The problem requires that each position maintains its original parity type. If position 0 had an even digit originally, it must contain an even digit in the final result. If position 1 had an odd digit, it must contain an odd digit in the final result.

Correct Understanding:

• For 2143: positions are [even, odd, even, odd]
• You can only place even digits in positions 0 and 2
• You can only place odd digits in positions 1 and 3
• Correct answer: 4321 (4 and 2 in even positions, 3 and 1 in odd positions)

Pitfall 2: Incorrect Parity Tracking with Index Decrementation

The Problem: When searching for the next available digit of the same parity, developers might incorrectly decrement by 1 instead of 2:

# WRONG - This would check digits of wrong parity
while digit_count[largest_available[parity]] == 0:
    largest_available[parity] -= 1  # Should be -= 2

Why It's Wrong: Decrementing by 1 would alternate between even and odd digits. For example, starting from 9 (odd), you'd check 8 (even), 7 (odd), etc., mixing parities.

Correct Approach: Always decrement by 2 to stay within the same parity:

• Odd sequence: 9 → 7 → 5 → 3 → 1
• Even sequence: 8 → 6 → 4 → 2 → 0

Pitfall 3: Edge Case with Leading Zeros

The Problem: If the input number starts with small even digits and has zeros, there's a theoretical concern about whether zeros could end up in the leading position.

Why It's Not Actually a Problem (but worth understanding): The problem states we're given a "positive integer", which by definition cannot start with 0. Additionally, our algorithm preserves positional parity, so if the original number didn't start with 0, the result won't either.

Example: For num = 2001:

• Positions: [even, even, even, odd]
• Available even digits: 2, 0, 0
• Available odd digit: 1
• Result: 2001 (the 2 naturally stays in front as it's the largest even digit)

Solution to Avoid These Pitfalls:

def largestInteger(self, num: int) -> int:
    digits = [int(c) for c in str(num)]
  
    # Separate digits by parity while preserving which positions need which parity
    odd_digits = sorted([d for d in digits if d % 2 == 1], reverse=True)
    even_digits = sorted([d for d in digits if d % 2 == 0], reverse=True)
  
    # Use iterators to track which digit to use next
    odd_iter = iter(odd_digits)
    even_iter = iter(even_digits)
  
    # Build result maintaining position-based parity
    result = []
    for original_digit in digits:
        if original_digit % 2 == 1:
            result.append(next(odd_iter))
        else:
            result.append(next(even_iter))
  
    return int(''.join(map(str, result)))

This alternative approach explicitly separates the sorting logic from the position-preservation logic, making the constraint clearer and reducing the chance of errors.