Largest Number After Digit Swaps by Parity

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.

2231. Largest Number After Digit Swaps by Parity

Difficulty: Easy

Link: LeetCode Problem

Problem Statement

You are given a positive number called num.

You can swap any two digits in num, but only if both digits have the same parity. This means:

• Both digits are even, or
• Both digits are odd.

You can do this swap as many times as you want.

Return the largest possible value of num after doing these swaps.

Solution

To solve this, we use two heaps:

• One max heap for the even digits.
• One max heap for the odd digits.

Here is how the solution works:

• First, we split the number into its digits.
• We put each digit into the correct heap. Even digits go into the even heap. Odd digits go into the odd heap.
• Then, we build the answer, one digit at a time, in the same order as the original number.
• For each position:
  • If the original digit was even, we take the largest remaining even digit from the even heap.
  • If the original digit was odd, we take the largest remaining odd digit from the odd heap.
• This way, the largest digits move to the left side of the number, since the left side has more value.

Code

var largestInteger = function(num) {
  const digits = num.toString().split('').map(Number);

  const evenHeap = new MaxHeap();
  const oddHeap = new MaxHeap();

  for (const d of digits) {
    if (d % 2 === 0) evenHeap.push(d);
    else oddHeap.push(d);
  }

  const result = [];
  for (const d of digits) {
    if (d % 2 === 0) result.push(evenHeap.pop());
    else result.push(oddHeap.pop());
  }

  return Number(result.join(''));
};