1675. Minimize Deviation in Array - Explanation

1. Sorting + Sliding Window

Intuition

Each element in the array can only take certain values: odd numbers can become themselves or double themselves, while even numbers can be halved repeatedly until they become odd. The key insight is that we can precompute all possible values each element can take, then find the smallest range that contains at least one value from each original element.

This transforms the problem into finding the smallest window in a sorted list of values where each original array element is represented at least once. We use a sliding window approach on the sorted list of all possible values, tracking which original elements are covered.

Algorithm

For each number in the input array, generate all possible values it can take:
- If odd: it can be itself or doubled (only once).
- If even: it can be halved repeatedly down to an odd number, plus all intermediate values.
Store each value paired with its original index.
Sort all these pairs by value.
Use a sliding window with two pointers i and j:
- Expand j to include more values and track how many original elements are covered.
- When all n elements are covered, shrink from i to minimize the window range.
- Update the result with the minimum difference between the largest and smallest values in valid windows.
Return the minimum deviation found.

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

Time & Space Complexity

Time complexity: $O((n \log m) * \log (n \log m))$
Space complexity: $O(n \log m)$

Where $n$ is the size of the array $nums$ and $m$ is the maximum element in $nums$ .

2. Min-Heap

Intuition

Instead of generating all possible values upfront, we can work incrementally. First, reduce every number to its minimum possible value (divide even numbers until they become odd). Then, we repeatedly try to increase the smallest element by doubling it (if possible), since increasing smaller values is the only way to reduce the deviation.

The min-heap lets us efficiently access the smallest current value. We track the maximum value in the heap separately. Each iteration, we pop the minimum, update our best deviation, and if that minimum can still be doubled, we push the doubled value back.

Algorithm

Reduce each number to its minimum form by dividing even numbers by 2 until odd. Track the maximum allowed value each element can reach.
Push each (current value, max allowed value) pair into a min-heap. Track the current maximum across all heap elements.
While the heap contains all elements:
- Pop the minimum value and compute the current deviation (max minus min).
- If this minimum can still increase (less than its max allowed), double it and push back.
- Update the tracked maximum if needed.
- If the minimum cannot increase, stop (we cannot reduce deviation further).
Return the minimum deviation found.

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

Time & Space Complexity

Time complexity: $O(n *\log n * \log m)$
Space complexity: $O(n)$

Where $n$ is the size of the array $nums$ and $m$ is the maximum element in $nums$ .

3. Max-Heap

Intuition

We can approach this from the opposite direction: start with all numbers at their maximum possible value, then repeatedly decrease the largest element. Odd numbers are first doubled to reach their maximum. Even numbers stay as they are initially.

Using a max-heap, we always have quick access to the current largest value. We track the minimum value separately. Each iteration, we halve the maximum (if even) and update our best deviation. The process stops when the maximum is odd, since odd numbers cannot be reduced.

Algorithm

For each number, if it is odd, double it. Push all values into a max-heap. Track the current minimum value.
While the heap is not empty:
- Pop the maximum value and compute the current deviation (max minus min).
- Update the result if this deviation is smaller.
- If the maximum is odd, stop (cannot reduce it further).
- Otherwise, halve the maximum, push it back, and update the minimum if needed.
Return the minimum deviation found.

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

Time & Space Complexity

Time complexity: $O(n *\log n * \log m)$
Space complexity: $O(n)$

Where $n$ is the size of the array $nums$ and $m$ is the maximum element in $nums$ .

Common Pitfalls

Confusing the Operations for Odd and Even Numbers

Odd numbers can only be doubled (multiplied by 2), while even numbers can only be halved (divided by 2). A frequent mistake is applying the wrong operation or allowing both operations on any number. Remember: odd numbers increase, even numbers decrease.

Not Recognizing the Stopping Condition

When using the max-heap approach, the algorithm must stop when the maximum element is odd because odd numbers cannot be reduced further. Failing to check this condition leads to infinite loops or attempting invalid operations.

Forgetting to Track the Minimum Value Separately

When using a max-heap, you only have direct access to the maximum element. The deviation requires knowing both the max and min values. A common error is trying to find the minimum by scanning the heap, which defeats the purpose of the data structure. Track the minimum separately and update it when pushing new values.

Not Generating All Possible Values for Each Element

In the sliding window approach, each number can take multiple values. Even numbers can be halved repeatedly until odd, and odd numbers can be doubled once. Missing any possible value means the algorithm might not find the true minimum deviation.

Off-by-One Errors in the Sliding Window Count

When using the sliding window with a frequency array, ensure you correctly track when all n original elements are represented. Incrementing or decrementing the count at the wrong time can cause the window to be considered valid prematurely or remain invalid when it should be valid.