Minimize Deviation in Array — Max-Heap Reduction Interview

Problem Statement#

Given an integer array nums, you can on any element:

• If even, divide by 2.
• If odd, multiply by 2. Minimize the deviation (max minus min) over any sequence of operations.

Constraints:

• 2 <= nums.length <= 5 * 10^4
• 1 <= nums[i] <= 10^9

Input:  nums = [1,2,3,4]
Output: 1

Input:  nums = [4,1,5,20,3]
Output: 3

Why This Problem Matters#

LeetCode 1675 is a Google, Amazon, and Microsoft hard interview problem. It tests the ability to reduce a two-directional optimization (you can grow or shrink each element) into a one-directional simulation that a max-heap can drive.

The trick — doubling odds upfront so every remaining op shrinks the max — is a high-leverage interview move. It is one of the cleanest priority queue interview reductions you will encounter.

The Core Insight#

For each odd, double it once and stop (you cannot make odd smaller). Now every value is even or has been doubled-from-odd; only halving operations remain, and only when an even number is greater than its original odd parent. Push all values into a max-heap, track the running min. Pop the max; if even, halve and push back; update min and best. Stop when the max is odd (cannot shrink further).

Visual Dry Run#

nums = [4,1,5,20,3] Doubled odds upfront: [4,2,10,20,6], min=2

Solution (Optimal)#

import heapq
from typing import List
 
class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        heap = []
        cur_min = float('inf')
        for x in nums:
            if x % 2 == 1:
                x *= 2
            heap.append(-x)
            cur_min = min(cur_min, x)
        heapq.heapify(heap)
        best = -heap[0] - cur_min
        while True:
            mx = -heapq.heappop(heap)
            best = min(best, mx - cur_min)
            if mx % 2 == 1:
                break
            half = mx // 2
            cur_min = min(cur_min, half)
            heapq.heappush(heap, -half)
        return best

class MaxHeap {
    constructor() { this.h = []; }
    push(v) { this.h.push(v); this._up(this.h.length - 1); }
    pop() {
        const top = this.h[0], last = this.h.pop();
        if (this.h.length) { this.h[0] = last; this._down(0); }
        return top;
    }
    peek() { return this.h[0]; }
    _up(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[i] > this.h[p]) { [this.h[i], this.h[p]] = [this.h[p], this.h[i]]; i = p; }
            else break;
        }
    }
    _down(i) {
        const n = this.h.length;
        while (true) {
            const l = 2 * i + 1, r = 2 * i + 2;
            let m = i;
            if (l < n && this.h[l] > this.h[m]) m = l;
            if (r < n && this.h[r] > this.h[m]) m = r;
            if (m === i) break;
            [this.h[i], this.h[m]] = [this.h[m], this.h[i]];
            i = m;
        }
    }
}
 
var minimumDeviation = function(nums) {
    const heap = new MaxHeap();
    let curMin = Infinity;
    for (let x of nums) {
        if (x % 2 === 1) x *= 2;
        heap.push(x);
        curMin = Math.min(curMin, x);
    }
    let best = heap.peek() - curMin;
    while (true) {
        const mx = heap.pop();
        best = Math.min(best, mx - curMin);
        if (mx % 2 === 1) break;
        const half = mx / 2;
        curMin = Math.min(curMin, half);
        heap.push(half);
    }
    return best;
};

Time: O(N log N log M) where M is the largest value — each value can halve at most log M times. Space: O(N) — heap.

Common Mistakes#

• Halving odds (impossible operation) — only doubling odds is allowed.
• Doubling odds repeatedly — once is enough; doubling further only grows the max.
• Forgetting to update cur_min after each halving (the new value can be the new min).
• Computing deviation only at the end; you must check after every step because the max shrinks.
• Stopping when cur_min is odd — wrong stopping condition; stop when the max is odd.

Interview Tips#

• Walk through the dual: think of every number as a power-of-two-times-odd-base; you choose any of those values.
• Show why doubling odds first turns this into a pure shrink-only simulation.
• Mention the alternative of using a TreeSet (sorted multiset) for O(N log N log M) — same complexity but different code.
• Discuss why min only ever decreases monotonically.

Follow-up Questions#

• What if every element can shrink and grow at most k times? Hint: heap with op-count tracking.
• Solve with a TreeSet/SortedList. Hint: same operations but easier to track min.
• Generalize to any allowed multipliers, not just 2. Hint: more states; harder.
• What if elements can be negative? Hint: redefine min/max bounds carefully.
• Find the operations sequence, not just the deviation. Hint: track ancestry per value.

Key Takeaways#

• LeetCode 1675 Minimize Deviation reduces to a max-heap shrink simulation by doubling odds upfront.
• Time: O(N log N log M). Space: O(N).
• The min only decreases as halving introduces smaller values.
• Stop the moment the max is odd; it cannot shrink further.
• This priority queue interview problem teaches a beautiful reduction.
• TreeSet is a valid alternative with the same complexity.
• Common at Google and Amazon hard interview rounds.