Minimize Deviation in Array: Max Heap Greedy Pattern

You are given an array nums of n positive integers. You can perform two types of operations on any element: if the element is even, divide it by 2; if the element is odd, multiply it by 2. The deviation of the array is max(nums) - min(nums). Return the minimum deviation the array can have after performing some number of operations.

This is LeetCode 1675: Minimize Deviation in Array.

Why this problem matters

Minimize Deviation in Array is one of the cleanest examples of a normalization-then-greedy pattern. The problem gives you two operations (multiply odd, divide even), and the core challenge is figuring out how to unify them into a single direction of movement. Once you see the normalization trick, the rest follows from a standard max-heap greedy loop.

This pattern appears whenever you need to minimize a range across a collection of values that can only move in constrained ways. It trains you to think about reducing problem complexity before reaching for a data structure, rather than trying to juggle multiple operations simultaneously.

Heap-based greedy is a building block that shows up across many hard problems. The idea of repeatedly shrinking the largest element, tracking the global minimum along the way, is the same skeleton used in problems like merge k sorted lists, sliding window median, and IPO. Mastering it here gives you a reusable template.

The key insight

Odd numbers can only be multiplied by 2 (go up), and they can only do this once before becoming even. Even numbers can only be divided by 2 (go down), potentially multiple times until they become odd. That asymmetry makes it hard to reason about both directions at once.

The trick: double every odd number first. After this normalization step, every element in the array is even (or was already even). Now the only operation you ever need is "divide the maximum by 2 if it is even." You have collapsed a two-operation problem into a one-operation problem.

With all elements normalized, throw them into a max-heap. Repeatedly pop the maximum, halve it (if even), and push the result back. Track the running minimum across all insertions. At each step, compute max - min and record the best deviation seen. Stop when the maximum is odd, because you cannot shrink it further.

The solution

import heapq

def minimizeDeviation(nums):
    heap = []
    min_val = float('inf')

    for num in nums:
        val = num * 2 if num % 2 == 1 else num
        min_val = min(min_val, val)
        heapq.heappush(heap, -val)

    best = -heap[0] - min_val

    while -heap[0] % 2 == 0:
        max_val = -heapq.heappop(heap)
        halved = max_val // 2
        min_val = min(min_val, halved)
        heapq.heappush(heap, -halved)
        best = min(best, -heap[0] - min_val)

    return best

Let's walk through the pieces.

First, the normalization loop. For every number in the input, if it is odd, double it. This gives each odd number its maximum possible value. We push the negated value into Python's min-heap (since Python only has a min-heap, negating simulates a max-heap). We also track min_val across all normalized values.

Then the greedy loop. Pop the largest element (negate to recover it). If it is even, halve it and push it back. Update min_val if the halved value is smaller. Compute the current deviation as current_max - min_val and update best. If the popped maximum is odd, we cannot halve it further, so the loop ends.

Visual walkthrough

Here is the full process on nums = [1, 2, 3, 4]. After normalizing (doubling odds), we get [2, 2, 6, 4]. The max-heap loop repeatedly shrinks the largest element until it cannot be halved anymore.

Notice how the deviation drops from 4 to 2 to 1 across the iterations. Each step shrinks the range by pulling the maximum closer to the rest of the array. When the maximum becomes odd, it is stuck, and we have our answer.

Complexity analysis

Each element can be halved at most log(max) times before it becomes odd and gets stuck. Each halving involves a heap pop and push, both O(log n). So the total work is O(n * log(max) * log n). The normalization step is O(n log n) for the initial heap construction. Space is O(n) for the heap.

The log(max) factor comes from the fact that each value can be divided by 2 at most log2(value) times. In the worst case, a value like 10^9 can be halved about 30 times. So in practice, the constant is small.

The building blocks

1. Normalization to unify operations

for num in nums:
    val = num * 2 if num % 2 == 1 else num
    min_val = min(min_val, val)
    heapq.heappush(heap, -val)

This step converts a two-operation problem into a single-operation problem. By pushing every element to its maximum reachable value upfront, you only need to consider "shrink the maximum" going forward. This is the same principle behind reducing search spaces in optimization: simplify the problem before solving it. Any time you face asymmetric operations, ask yourself whether you can normalize one direction away.

2. Greedy max-heap shrinking

while -heap[0] % 2 == 0:
    max_val = -heapq.heappop(heap)
    halved = max_val // 2
    min_val = min(min_val, halved)
    heapq.heappush(heap, -halved)
    best = min(best, -heap[0] - min_val)

The greedy invariant: at every step, halving the current maximum is the best way to reduce the deviation. Why? The deviation is max - min. You cannot increase the minimum (all elements are at their max after normalization). The only move is to decrease the maximum. The heap gives you the maximum in O(log n), and you greedily shrink it. This pattern of "repeatedly operate on the extremum" is the foundation of many heap-based greedy algorithms.

Edge cases

• All elements identical. nums = [5, 5, 5]. After doubling, [10, 10, 10]. Deviation is 0 immediately.
• Single element. nums = [7]. Deviation is always 0.
• All odd. nums = [1, 3, 5]. After doubling, [2, 6, 10]. The algorithm halves from the top until it hits an odd max.
• All even. nums = [2, 4, 8]. No normalization needed. The algorithm halves the max directly.
• Large values. Elements up to 10^9 are fine since each halves at most ~30 times.
• Already minimal. nums = [2, 3]. After doubling odds, [2, 6]. Halve 6 to 3. Deviation = 3 - 2 = 1. 3 is odd, stop. Answer = 1.

From understanding to recall

The normalization step is the part that makes or breaks this problem. Without it, you are stuck trying to decide whether to multiply odd numbers or divide even numbers at each step, and the search space explodes. With it, the algorithm is a clean loop: pop the max, halve if even, stop if odd.

The tricky detail to remember is that Python's heapq is a min-heap, so you negate values to simulate a max-heap. That is a mechanical detail, but it is the kind of thing that trips you up under pressure. Spaced repetition lets you type this pattern from scratch enough times that the negation becomes automatic, and you can focus your mental energy on the actual problem-solving.

Related posts

• Kth Largest Element in an Array - Another heap pattern where you maintain a size-k heap to efficiently track order statistics
• IPO - Uses two heaps to greedily pick the most profitable project, a similar "operate on the extremum" pattern
• Sliding Window Median - Dual-heap approach for maintaining a running median, extending the heap toolkit

CodeBricks breaks this problem into its two building blocks (normalization and heap-based greedy shrinking) and drills them independently. You practice the normalize-then-shrink pattern on its own schedule, so when you see a new problem with asymmetric operations, the reduction is second nature.