Minimize Deviation in Array - Video Solutions

Problem Overview: You are given an integer array where two operations are allowed: divide an even number by 2 or multiply an odd number by 2. The goal is to minimize the difference between the maximum and minimum elements after performing any number of these operations.

The challenge is that each number can move within a range of values depending on the operations applied. Instead of trying all combinations, the key is to normalize values and always reduce the current maximum while tracking the minimum.

Approach 1: Greedy with Max-Heap (O(n log n * log M) time, O(n) space)

This is the standard optimal approach using a heap (priority queue). First normalize the array: convert every odd number into an even number by multiplying it by 2. This ensures every element can only move downward (via division by 2). Push all values into a max-heap and track the current minimum value in the array.

At each step, extract the maximum element and update the deviation using max - min. If the maximum is even, divide it by 2 and push it back into the heap, updating the minimum if needed. This greedy step works because reducing the current maximum is the only operation that can potentially shrink the deviation. The process stops when the maximum becomes odd, since it cannot be reduced further.

This method combines greedy reasoning with efficient max retrieval from a heap. Every element can be halved only a limited number of times, giving an overall complexity of O(n log n * log M), where M is the maximum value.

Approach 2: Dynamic Adjustment with Ordered Set (O(n log n * log M) time, O(n) space)

Another implementation uses an ordered set or balanced BST to maintain elements in sorted order. Similar to the heap strategy, first normalize the array by doubling all odd values so that every number starts as even.

Insert all elements into the ordered structure. The smallest element is always accessible from the beginning of the set, while the largest comes from the end. Compute the deviation using these two values. If the largest value is even, divide it by 2 and insert the updated value back into the set. Each adjustment dynamically changes the range of the array.

The ordered set automatically maintains sorted order, making it easy to recompute the min and max after every modification. This approach is conceptually similar to the heap method but uses ordered containers instead of a priority queue.

Recommended for interviews: The greedy max-heap approach is what interviewers typically expect. It shows you can combine normalization, priority queues, and greedy reasoning to iteratively tighten the range. Mentioning the ordered set alternative demonstrates deeper understanding of data structure tradeoffs, but the heap solution is simpler and more common in production code.