1675. Minimize Deviation in Array

Observations:

an odd number a can be transformed to 2*a or a only
an even number b can only be decreased to b/2

Steps:

change all odd numbers to even at the beginning and this would not impact the final result since those odd numbers can be converted back
find the max in heap and divid by 2 can potentially decrease deviation (eg, max is decreased while min remains the same)
Stop once max is odd. Proof:
1. there are 2 ways to decrease deviation: increase min and decrease max
2. Once max is odd, you cannot decrease it anymore
3. if min is even, you cannot increase it
4. if min is odd, 2*min must be last max so increasing it will produce a sequence we have processed already

class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        pq = [-num * (1 + num%2) for num in nums]
        heapq.heapify(pq)
        
        cur_min = -max(pq)
        res = float("inf")
        while True:
            cur_max = heapq.heappop(pq)
            res = min(res, -cur_max - cur_min)
            if cur_max % 2:
                return res
            else:
                next_element = cur_max // 2
                cur_min = min(cur_min, -next_element)
                heapq.heappush(pq, cur_max // 2)

1675. Minimize Deviation in Array - cocoder39/coco39_LC GitHub Wiki