Leetcode: 1675. Minimize Deviation in Array

Problem Statement

Can we simplify the problem while keeping it the same? In the original problem, you can either divide (decrease) even number or multiply (increase) odd numbers. As there is no need to minimize the number of operations, we can divide all numbers as much as we can and solve the problem where we will only increase the numbers. Each turn, we remove the smallest element and add it's double back to the Priority-Queue. We keep the maximum after each update. This will be enough for us to compute the shortest interval that contains at least one of each given numbers. Time complexity is \(O(n \log n)\) and space is \(O(n)\). 

class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0

        seen = set()
        min_pq = []
        max_pq = []

        def push(a, b):
            if (a, b) not in seen:
                heappush(min_pq, (a, b))
                heappush(max_pq, (-a, b))
                seen.add((a, b))

        def pop():
            a, b = heappop(min_pq)
            seen.remove((a, b))
            while len(max_pq) > 0 and (-max_pq[0][0], max_pq[0][1]) not in seen:
                heappop(max_pq)
            return (a, b)

        k = 0
        for i in nums:
            if i % 2 == 1:
                push(i, i * 2)
                k += 2
            else:
                j = i
                while j % 2 == 0 and j > 0:
                    j = j // 2
                    k += 1
                push(j, i)
                k += 1

        ans = -max_pq[0][0] - min_pq[0][0]
        for i in range(k):
            cur = -max_pq[0][0] - min_pq[0][0]
            ans = min(ans, cur)
            left, right = pop()
            if left * 2 <= right:
                push(left * 2, right)
            else:
                push(left, right)

        return ans

Cited by 1