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.length2 <= n <= 5 * 10^41 <= nums[i] <= 10^8
Hints for Minimize Deviation in Array
Hint 1
An odd number can be doubled exactly once — after that it is even and can only be halved.
Hint 2
So double every odd number up front; then every element can only shrink.
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
- Replace every odd
vwith2vand build a max-heap. - Track the running minimum and record the current deviation.
- While the maximum is even, halve it, update the minimum if the half is smaller, re-heapify and record the deviation again.
- 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 bestJava
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