To make the number larger, we want to move bigger digits to the left. We can move a digit to the left via swap only if the target index has a same-parity digit. In other words, as we scan num from left to right, we want to pick the largest digit with matching parity.
We keep two max heaps: one for odd digits and one for even digits.
There are 
Time: 
from heapq import heapify, heappush as push, heappop as pop
class Solution:
def largestInteger(self, num: int) -> int:
is_even = lambda x: x % 2 == 0
digits = [int(d) for d in list(str(num))]
odd_max_heap = [-d for d in digits if not is_even(d)]
heapify(odd_max_heap)
even_max_heap = [-d for d in digits if is_even(d)]
heapify(even_max_heap)
largest = 0
for d in digits:
d2 = -pop(even_max_heap) if is_even(d) else -pop(odd_max_heap)
largest = 10 * largest + d2
return largest
unreasonably effective 
Leave a comment