Minimize Deviation in Array

How it works

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.

Steps

1. For each number, if it is odd, double it. Push all values into a max-heap. Track the current minimum value.
2. 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.
3. Return the minimum deviation found.

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.

Things to watch for

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.

from typing import List
import heapq

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

class Solution {
public:
    int minimumDeviation(vector<int>& nums) {
        priority_queue<int> maxHeap;
        int minVal = INT_MAX;

        for (int num : nums) {
            if (num % 2 == 1) num *= 2;
            maxHeap.push(num);
            minVal = min(minVal, num);
        }

        int res = INT_MAX;

        while (!maxHeap.empty()) {
            int maxVal = maxHeap.top();
            maxHeap.pop();
            res = min(res, maxVal - minVal);

            if (maxVal % 2 == 1) break;

            int nextVal = maxVal / 2;
            maxHeap.push(nextVal);
            minVal = min(minVal, nextVal);
        }

        return res;
    }
};