1675. Minimize Deviation in Array - Explanation

class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        n = len(nums)
        arr = []
        for i, num in enumerate(nums):
            if num & 1:
                arr.append((num, i))
                arr.append((num * 2, i))
            else:
                while num % 2 == 0:
                    arr.append((num, i))
                    num //= 2
                arr.append((num, i))

        arr.sort()
        res = float("inf")

        seen = [0] * n
        count = i = 0
        for j in range(len(arr)):
            seen[arr[j][1]] += 1
            if seen[arr[j][1]] == 1:
                count += 1
                while count == n:
                    res = min(res, arr[j][0] - arr[i][0])
                    seen[arr[i][1]] -= 1
                    if seen[arr[i][1]] == 0:
                        count -= 1
                    i += 1

        return res

class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        minHeap, heapMax = [], 0

        for n in nums:
            tmp = n
            while n % 2 == 0:
                n //= 2
            minHeap.append((n, max(tmp, 2 * n)))
            heapMax = max(heapMax, n)

        res = float("inf")
        heapq.heapify(minHeap)

        while len(minHeap) == len(nums):
            n, nMax = heapq.heappop(minHeap)
            res = min(res, heapMax - n)

            if n < nMax:
                heapq.heappush(minHeap, (n * 2, nMax))
                heapMax = max(heapMax, n * 2)

        return res

class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        maxHeap = []
        minVal = float("inf")

        for num in nums:
            if num % 2 == 1:
                num *= 2
            heapq.heappush(maxHeap, -num)
            minVal = min(minVal, num)

        res = float("inf")

        while maxHeap:
            maxVal = -heapq.heappop(maxHeap)
            res = min(res, maxVal - minVal)
            if maxVal % 2 == 1:
                break

            nextVal = maxVal // 2
            heapq.heappush(maxHeap, -nextVal)
            minVal = min(minVal, nextVal)

        return res