This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #1675 (Medium): Minimize Deviation in Array
Description:
You are given an array nums of n positive integers.
You can perform two types of operations on any element of the array any number of times:

If the element is even, divide it by 2.
 For example, if the array is [1,2,3,4], then you can do this operation on the last element, and the array will be [1,2,3,2].

If the element is odd, multiply it by 2.
 For example, if the array is [1,2,3,4], then you can do this operation on the first element, and the array will be [2,2,3,4].
The deviation of the array is the maximum difference between any two elements in the array.
Return the minimum deviation the array can have after performing some number of operations.
Examples:
Example 1:  

Input:  nums = [1,2,3,4] 
Output:  1 
Explanation:  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 
Explanation:  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 
Constraints:
 n == nums.length
 2 <= n <= 105
 1 <= nums[i] <= 109
Idea:
The hints in this case are a little backwards. Since it's only ever possible to perform the multiply operation once (as the number will then be an even number), but you can potentially perform the division operation many times, it's far better to start from the maximum value for each nums[i] and work downward.
If you started from the minimum value, as the hints suggest, then you'd have to separately keep track of the max value for each element so that you don't multiply past that amount while moving upward.
The idea is actually very simple from there. Find the max possible value for each nums[i], then keep taking the largest one and dividing by 2 if it's even. At each step, check to see if you've found a new best ans (highest value  lowest value). If the largest number is odd, you can't divide it by 2, which means it's impossible to reach a better number than you've already found, so return your best ans.
Implementation:
Since we need sorted data, but we only ever need the modify the max value at any time, we should use a maxheap or priority queue structure. We will need the smallest value of nums, but we don't actually need to modify that element, so we can just keep track of it in min as we go.
First, we need to iterate through nums, multiply any odd numbers by 2, then insert them into heap or pq while making sure to update min if necessary.
Then, while the largest value in heap/pq is even, we can take it out, divide it by 2, update our ans and min if necessary, and reinsert it back into the heap/pq.
Once we reach an odd number at the top of heap/pq, return the best ans.
Javascript Code w/ MaxPriorityQueue():
This code is easier to read, but less efficient. It takes advantage of the PriorityQueue npm package that leetcode includes by default with their javascript implementation.
var minimumDeviation = function(nums) {
let pq = new MaxPriorityQueue({priority: x => x})
for (let n of nums) {
if (n % 2) n *= 2
pq.enqueue(n)
}
let ans = pq.front().element  pq.back().element
while (pq.front().element % 2 === 0) {
pq.enqueue(pq.dequeue().element / 2)
ans = Math.min(ans, pq.front().element  pq.back().element)
}
return ans
};
Javascript Code w/ MaxHeap Implementation:
var minimumDeviation = function(nums) {
let len = nums.length, min = Infinity,
heap = new Uint32Array(len+1), hix = 1
heap[0] = 2e9
const heapify = val => {
let i = hix, par = i >> 1, temp
heap[hix++] = val
while (heap[par] < heap[i]) {
temp = heap[par], heap[par] = heap[i], heap[i] = temp
i = par, par = i >> 1
}
}
const extract = () => {
let max = heap[1], left, right, temp,
i = 1, child = heap[3] > heap[2] ? 3 : 2
heap[1] = heap[hix], heap[hix] = 0
while (heap[i] < heap[child]) {
temp = heap[child], heap[child] = heap[i], heap[i] = temp
i = child, left = i << 1, right = left + 1
child = heap[right] > heap[left] ? right : left
}
return max
}
for (let i = 0, n = nums[0]; i < len; n = nums[++i]) {
if (n % 2) n *= 2
if (n < min) min = n
heapify(n)
}
let curr = extract(), ans = curr  min
while (curr % 2 === 0) {
curr /= 2
if (curr < min) min = curr
heapify(curr)
curr = extract()
ans = Math.min(ans, curr  min)
}
return ans
};
Top comments (2)
shouldn't the 3rd example in the question be 1 ? as the array will be [4,5,4]
Unfortunately, the only operation available for even numbers is to divide by two, so you wouldn't be able to multiply the first element
2
by two to get4
.That makes the optimal result
[2,5,4]
or[2,5,2]
.