#1675

Hard

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimize Deviation in Array

Given a positive integer array, repeatedly double or halve elements to minimize the difference between its largest and smallest values.

array greedy heap priority queue ordered set

Problem Statement

You are given an array of positive integers nums. You can perform two operations any number of times: multiply an odd number by 2 or divide an even number by 2. The goal is to minimize the deviation of the array, defined as the difference between the maximum and minimum elements.

Return the minimum possible deviation after applying the allowed operations optimally. Each operation changes the array while respecting the invariant that odd numbers can only be doubled and even numbers can be repeatedly halved until they become odd.

Examples

Example 1

Input: nums = [1,2,3,4]

Output: 1

You can transform the array to [1,2,3,2], then to [2,2,3,2], then the deviation will be 3 - 2 = 1.

Example 2

Input: nums = [4,1,5,20,3]

Output: 3

You can transform the array after two operations to [4,2,5,5,3], then the deviation will be 5 - 2 = 3.

Example 3

Input: nums = [2,10,8]

Output: 3

Example details omitted.

Constraints

n == nums.length
2 <= n <= 5 * 104
1 <= nums[i] <= 109

Solution Approach

Normalize All Numbers to Even

Transform each number to its smallest possible value by halving even numbers. This ensures the array starts at an invariant baseline where all numbers are as low as possible for deviation calculation.

Use a Max-Heap to Track Maximum

Push all numbers into a max-heap and track the current minimum. Continuously extract the maximum element and halve it if it is even, updating the current minimum and deviation. This greedy choice ensures we always target the largest contributor to deviation first.

Stop When Maximum Cannot Be Reduced

Once the top of the heap is odd, no further halving is possible. At this point, the current deviation is the smallest achievable, as every previous operation maintained the array invariant and reduced the largest element whenever possible.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) due to heap operations performed for each element at most log(max(nums)) times. Space complexity is O(n) for storing the heap and tracking the minimum element.

What Interviewers Usually Probe

Candidates who attempt naive sorting without heap will likely hit timeouts.
Look for recognition that the greedy approach must focus on the maximum element while preserving array invariants.
Ensure they understand why odd numbers are only multiplied once and even numbers can be repeatedly halved.

Common Pitfalls or Variants

Common pitfalls

Failing to normalize odd numbers initially, causing incorrect deviation calculation.
Using a min-heap instead of a max-heap, which reverses the greedy strategy.
Not updating the current minimum when halving the maximum, leading to wrong deviation results.

Follow-up variants

Minimize deviation with additional constraint on number of operations allowed.
Find maximum deviation instead of minimum after allowed operations.
Solve for arrays containing zeros and ones with same doubling/halving rules.

FAQ

What is the main strategy to solve Minimize Deviation in Array?

The key strategy is to normalize numbers to their minimum even forms and then repeatedly halve the maximum using a max-heap, ensuring the deviation decreases optimally.

Why do we use a max-heap instead of a min-heap?

A max-heap efficiently tracks the current largest number, which is the primary contributor to deviation, allowing the greedy halving operation to reduce deviation correctly.

How do odd and even numbers differ in allowed operations?

Odd numbers can only be multiplied by 2 once to become even, while even numbers can be repeatedly halved until they turn odd. This invariant drives the solution's correctness.

What is the time complexity of this approach?

Time complexity is O(n log n * log(maxNum)) because each element can be pushed and popped from the heap multiple times proportional to the number of times it can be halved.

Can this approach handle large arrays up to 5*10^4 elements?

Yes, by using a heap and the greedy halving strategy, it efficiently reduces deviation without sorting the entire array multiple times, scaling to the problem's constraints.

terminal

Solution

Solution 1: Greedy + Priority Queue

Intuitively, to get the minimum offset of the array, we need to decrease the maximum value of the array and increase the minimum value of the array.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        h = []
        mi = inf
        for v in nums:
            if v & 1:
                v <<= 1
            h.append(-v)
            mi = min(mi, v)
        heapify(h)
        ans = -h[0] - mi
        while h[0] % 2 == 0:
            x = heappop(h) // 2
            heappush(h, x)
            mi = min(mi, -x)
            ans = min(ans, -h[0] - mi)
        return ans

Continue Practicing

#1606 find servers that handled most number of requests #1686 stone game vi #1648 sell diminishing valued colored balls