Minimize Deviation in Array — Hard Problem & Solution

Problem statement

You may repeatedly apply either operation to any element: double an odd element, or halve an even one.

The deviation of the array is the difference between its largest and smallest element. Return the smallest deviation reachable.

Example 1

Input: nums = [1,2,3,4]
Output: 1
Explanation: Reach `[2,2,3,4] → [2,2,3,2]`, whose deviation is 1.

Example 2

Input: nums = [4,1,5,20,3]
Output: 3
Explanation: Reach `[4,2,5,5,6]`.

Example 3

Input: nums = [2,10,8]
Output: 3

Constraints

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

How to solve Minimize Deviation in Array

Normalise by doubling every odd element, so from then on the only move is halving. Then repeatedly halve the maximum, which is the only move that can reduce the deviation, and record the best gap seen.

Approach

1. Replace every odd v with 2v and build a max-heap.
2. Track the running minimum and record the current deviation.
3. While the maximum is even, halve it, update the minimum if the half is smaller, re-heapify and record the deviation again.
4. Stop when the maximum is odd — it can no longer shrink.

Why it works

Doubling the odds first is what makes the state space finite and one-directional: afterwards every value only ever decreases, so the process must terminate. Halving the maximum is the only move that can help, because halving anything else leaves the maximum where it is while risking a smaller minimum. An odd maximum is the stopping point, since doubling it would only widen the gap.

Complexity

• Time — O(n log n log(maxValue))
• Space — O(n)

Pitfalls

• Forgetting to double the odds first misses reachable states.
• The minimum must be tracked separately; the max-heap does not expose it.
• Values double to 2 × 10^8, which still fits a 32-bit int but leaves little room.

Reference solution

Python

from typing import List
import heapq

def minimumDeviation(nums: List[int]) -> int:
    heap = [-(v * 2 if v % 2 == 1 else v) for v in nums]
    heapq.heapify(heap)
    mn = -max(heap)
    best = -heap[0] - mn
    while -heap[0] % 2 == 0:
        top = -heapq.heappop(heap)
        half = top // 2
        mn = min(mn, half)
        heapq.heappush(heap, -half)
        best = min(best, -heap[0] - mn)
    return best

JavaScript

var minimumDeviation = function(nums) {
    var heap = [], i;
    for (i = 0; i < nums.length; i++) heap.push(nums[i] % 2 === 1 ? nums[i] * 2 : nums[i]);
    var sift = function(j) {
        for (;;) {
            var l = 2 * j + 1, r = l + 1, s = j;
            if (l < heap.length && heap[l] > heap[s]) s = l;
            if (r < heap.length && heap[r] > heap[s]) s = r;
            if (s === j) break;
            var t = heap[s]; heap[s] = heap[j]; heap[j] = t;
            j = s;
        }
    };
    for (i = Math.floor(heap.length / 2) - 1; i >= 0; i--) sift(i);
    var mn = heap[0];
    for (i = 1; i < heap.length; i++) if (heap[i] < mn) mn = heap[i];
    var best = heap[0] - mn;
    while (heap[0] % 2 === 0) {
        var half = heap[0] / 2;
        if (half < mn) mn = half;
        heap[0] = half;
        sift(0);
        var gap = heap[0] - mn;
        if (gap < best) best = gap;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Count Ways to Make Array With Product Hard
• The Number of Good Subsets Hard
• Number of Ways to Reorder Array to Get Same BST Hard
• Make Array Strictly Increasing Hard
• Odd Even Jump Hard
• Maximum Number of Events That Can Be Attended II Hard