NeetCode #537LC-1675HardHeap / Priority Queue
← Back to All Problems#537 · #1675 · Minimize Deviation in Array(最小化数组中的最大值)
📌 Problem Statement & Constraints
You are given an array
nums of positive integers. You may divide any even number by 2, or multiply any odd number by 2, any number of times. Return the minimum possible deviation: the maximum minus the minimum value in the array. Constraints: 1 <= nums.length <= 5 * 10^4, 1 <= nums[i] <= 10^9.💡 Core Algorithmic Approaches
- First make every value even by doubling the odds -- after that, only divisions by 2 are available, which always decrease a value.
- The deviation is
max - min, so keep the maximum in a max-heap and track the running minimum. - Repeatedly halve the current maximum (it must be even), update the minimum, and record the deviation.
- Stop when the maximum becomes odd, since it can no longer be reduced.
💻 Benchmark Python3 Implementation
class Solution:
def minimumDeviation(self, nums: List[int]) -> int:
import heapq
# make everything even: only divisions by 2 remain available
nums = [x * 2 if x % 2 else x for x in nums]
h = [-x for x in nums]
heapq.heapify(h)
mn = min(nums)
best = -h[0] - mn # current deviation
while -h[0] % 2 == 0: # the maximum can still be halved
mx = -heapq.heappop(h)
mx //= 2
heapq.heappush(h, -mx)
mn = min(mn, mx) # the minimum may have decreased
best = min(best, -h[0] - mn)
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n log V): each halving costs O(log n) and there are at most log V per element.
💾 Space Complexity
O(n) for the heap.
⚠️ Interview Pitfalls & Follow-ups
- Leaving odd values alone: doubling them first is what makes the halving-only reduction possible.
- Forgetting to update the minimum: halving the maximum can push a value below the current minimum, which shrinks the deviation.
- Continuing to halve an odd maximum: it cannot be divided further, so the loop must stop.
- Tracking only the maximum: the deviation needs both ends.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.