Minimize Deviation in Array

Hard
976.

Minimize Deviation in Array

Minimize Deviation in Array is a hard coding problem on arrays, greedy and heap, asked in Amazon, Google and Uber interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumDeviation = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimize Deviation in Array — Solution in Python, Java & C++

Minimize Deviation in Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimize Deviation in Array is a hard coding problem on arrays, greedy and heap, asked in Amazon, Google and Uber interviews.

  • Difficulty: Hard
  • Topics: Arrays, Greedy, Heap, Ordered Set
  • Asked at: Amazon, Google, Uber
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Minimize Deviation in Array

  1. Hint 1

    An odd number can be doubled exactly once — after that it is even and can only be halved.

  2. Hint 2

    So double every odd number up front; then every element can only shrink.

  3. Hint 3

    Repeatedly halve the current maximum, recording the deviation each time, until the maximum is odd.

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

Java

public static int minimumDeviation(int[] nums) {
    PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.reverseOrder());
    int mn = Integer.MAX_VALUE;
    for (int v : nums) {
        int w = (v % 2 == 1) ? v * 2 : v;
        heap.add(w);
        mn = Math.min(mn, w);
    }
    int best = heap.peek() - mn;
    while (heap.peek() % 2 == 0) {
        int top = heap.poll();
        int half = top / 2;
        mn = Math.min(mn, half);
        heap.add(half);
        best = Math.min(best, heap.peek() - mn);
    }
    return best;
}

C++

int minimumDeviation(vector<int>& nums) {
    priority_queue<int> heap;
    int mn = INT_MAX;
    for (int v : nums) {
        int w = (v % 2 == 1) ? v * 2 : v;
        heap.push(w);
        mn = min(mn, w);
    }
    int best = heap.top() - mn;
    while (heap.top() % 2 == 0) {
        int top = heap.top();
        heap.pop();
        int half = top / 2;
        mn = min(mn, half);
        heap.push(half);
        best = min(best, heap.top() - 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms