← Back to Sorting Pattern

📚 Largest Number After Digit Swaps by Parity – Java Cheat Sheet

📌 What Is It?

The problem involves rearranging the digits of a number such that the resulting number is the largest possible while maintaining the parity of each digit. Parity means:

• Even digits can only swap with other even digits.
• Odd digits can only swap with other odd digits.

The solution involves separating the digits by parity, sorting them in descending order, and reconstructing the number.

🧱 Pattern Template

class Solution {
    public int largestInteger(int num) {
        // Convert the number to a character array
        char[] digits = String.valueOf(num).toCharArray();

        // Separate even and odd digits
        List<Integer> evens = new ArrayList<>();
        List<Integer> odds = new ArrayList<>();

        for (char digit : digits) {
            int d = digit - '0';
            if (d % 2 == 0) {
                evens.add(d);
            } else {
                odds.add(d);
            }
        }

        // Sort even and odd digits in descending order
        evens.sort(Collections.reverseOrder());
        odds.sort(Collections.reverseOrder());

        // Reconstruct the largest number
        StringBuilder result = new StringBuilder();
        int evenIndex = 0, oddIndex = 0;

        for (char digit : digits) {
            int d = digit - '0';
            if (d % 2 == 0) {
                result.append(evens.get(evenIndex++));
            } else {
                result.append(odds.get(oddIndex++));
            }
        }

        return Integer.parseInt(result.toString());
    }
}

📊 Time Complexity

• Separating Digits: O(n) – Iterating through the digits of the number.
• Sorting Digits: O(n log n) – Sorting the even and odd digits.
• Reconstructing the Number: O(n) – Rebuilding the number from the sorted digits.
• Overall Complexity: O(n log n).

✅ Use Cases

• Rearranging digits to maximize or minimize a number
• Maintaining specific constraints while sorting
• Applications in combinatorics and number theory

📘 Common LeetCode Problems

• 2231. Largest Number After Digit Swaps by Parity [Easy] Sorting

🧪 Example: Largest Number After Digit Swaps by Parity

Input: num = 65875
Output: 87655

Explanation:
- Even digits: [6, 8]
- Odd digits: [5, 7, 5]
- Rearrange evens: [8, 6]
- Rearrange odds: [7, 5, 5]
- Reconstruct: 87655

💡 Pro Tips

• Use separate lists for even and odd digits to simplify sorting and reconstruction.
• Edge cases: single-digit numbers, all even or all odd digits.
• Ensure the result fits within the range of a 32-bit integer.