1675. Minimize Deviation in Array

HardGreedyArrayOrdered SetHeap (Priority Queue)

Problem Description

In this problem, we are provided with an array called nums consisting of n positive integers. The main objective is to perform certain operations on the elements of the array to achieve the minimum possible "deviation."

Deviation is defined as the maximum difference between any two elements in the array. We want to minimize this deviation by performing operations on the array elements according to these rules:

If an element is even, we can divide it by 2.
If an element is odd, we can multiply it by 2.

These operations can be applied to any element any number of times. The goal is to find out the smallest possible deviation that can be obtained after performing these operations.

Intuition

To solve this problem, we need to consider the effects of the defined operations on the elements of the array. Multiplying an odd number by 2 will always make it even, and dividing an even number by 2 can potentially make it smaller and closer to other numbers in the array. However, an odd number cannot be reduced further by these operations after it has been doubled. The intuition behind the solution exploits these properties.

Here are the steps to arrive at the intuition:

To minimize the deviation, we would like all the numbers to be as close to each other as possible.
Increasing the smallest element or decreasing the largest element would bring us closer to the goal.
Since we can't decrease an odd number and doubling it gives us more future flexibility (as the result is an even number), we initially double all the odd numbers in the array.
Once all numbers are even, we have the option to reduce the largest elements by dividing them by 2. This is the key operation, as it can potentially lower the deviation.
We should keep reducing the largest number until we can no longer reduce it (i.e., until it becomes odd).
We need to keep track of the smallest number encountered during the process since the deviation depends on both the smallest and largest numbers in the array.
A heap (priority queue) is perfect for this purpose because it allows us to efficiently extract the largest element and to add new elements.

By following these steps, we can incrementally decrease the array's deviation until we are left with the minimal possible deviation.

The solution code implements this intuition in Python, using a min-heap (by storing the negative of the values) to always pop the current largest element (most negative value) and implementing the described operations to reduce the deviation.

Learn more about Greedy and Heap (Priority Queue) patterns.

Solution Approach

The implementation of the solution follows a well-structured approach using a min-heap data structure to efficiently manage the elements while minimizing the deviation. The steps in the solution code can be broken down as follows:

Initialize an empty list called h which will serve as our min-heap, and a variable mi to store the minimum value in nums, initially set to infinity.
Iterate over the array nums and for each value v in nums:
- If v is odd (which is tested using the bitwise AND operator v & 1), it is doubled using the left shift operator (v <<= 1). This is done to ensure that we have the flexibility to divide it later on.
- Add the negative of each value to the heap, h. We use the negative because Python’s heapq module provides a min-heap that gives the smallest value. By inserting the negative of our values, we can simulate the behavior of a max-heap, which is necessary to efficiently retrieve the largest element.
- Update mi to be the minimum between mi and the current value v.
Transform the list h into a heap in place using heapify(h).
Initialize a variable ans to store the minimum deviation, it's set to the difference between the smallest value (mi) and the largest value (-h[0], which we take the negative of because we stored negative values in the heap).
Loop until the current largest element (h[0], the first element in the heap) is odd. Since we are storing negatives, for an actual element to be even, its negative must be divisible by 2, which we check by evaluating h[0] % 2 == 0. Inside the loop:
- Extract the largest element from the heap by popping the heap (x = heappop(h)), divide x by 2 (since x is negative, dividing by two makes it larger in absolute value but smaller in actual value since negative), and push it back into the heap (heappush(h, x)).
- Update mi if the new value -x (actual value due to negation) is smaller.
- Adjust ans to be the new minimum deviation if needed, which is the difference between -h[0] (since we stored negatives, this now represents the current largest actual value) and mi.
Finally, return ans as the result, which holds the minimum deviation after performing the operations.

The approach efficiently tracks the largest and smallest values in the heap, allowing the solution to converge to the minimum deviation by selectively doubling odd numbers once and halving even numbers until they become odd.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider the array nums with the following integers: [6, 2, 3, 4]. We'll walk through each step of the solution approach to demonstrate how we minimize the deviation.

Step 1 & 2: Convert all odd numbers to even by doubling and initialize the min-heap:

Since 3 is odd, we double it to get 6.
Now all elements are even: [6, 2, 6, 4].
We add their negative values to our min-heap h: [-6, -2, -6, -4]
Our minimum value mi is 2 (the smallest element in nums).

Step 3: Heapify the list h to convert it into a min-heap. Heap h looks like [-6, -4, -6, -2] after heapifying (min-heap of negative values effectively acts as a max-heap for their absolute values).

Step 4: Initialize ans for the minimum deviation, which is max(nums) - mi, which equates to 6 - 2 = 4.

Step 5: Loop until the largest element is odd (in terms of absolute values for stored negatives). The largest element is -6 (actual value 6).

Pop -6 from the heap, divide it by 2 (absolute value operation), and get -3 (reflecting actual value 3), which is then pushed back onto the heap.
The new heap is [-4, -2, -6, -3] when re-heapified. The smallest value so far remains 2. The largest element is now -4 (actual value 4), and ans is potentially updated to 4 - 2 = 2.
The process continues, and now -4 is the current largest element in the heap. Pop it out, divide it by 2, and we get -2. Now the heap has the elements [-3, -2, -6, -2]. The smallest value we have is still 2, and ans remains 2.
None of the remaining elements can now be divided by 2 since they are all odd (in terms of absolute values), so the loop ends.

Step 6: The final ans reflects our minimum deviation, which remains 2.

Through this example, we can see how the solution makes use of doubling the odd numbers and halving the even numbers while keeping track of the maximum and minimum values using a heap structure to arrive at the smallest possible deviation.

Solution Implementation

1import heapq
2
3class Solution:
4    def minimumDeviation(self, nums: List[int]) -> int:
5        # Initialize a max heap (using negative values because Python has a min heap by default)
6        max_heap = []
7        # Initialize the minimum value with infinity to find the minimum more easily later
8        min_value = float('inf')
9      
10        # Convert all integers to their potential maximum values and find the initial minimum
11        for value in nums:
12            if value % 2 == 1:  # If the value is odd
13                value <<= 1  # Double it to make it even (which can later be halved)
14            max_heap.append(-value)  # Add negative value to max_heap to maintain max heap property
15            min_value = min(min_value, value)  # Update the minimum value if necessary
16      
17        # Transform the list `max_heap` into a heap in-place
18        heapq.heapify(max_heap)
19      
20        # Initial answer is the difference between the largest (smallest negative) and the smallest value
21        answer = -max_heap[0] - min_value
22      
23        # While the smallest negative value (largest original value) on the heap is even
24        # it can be halved to potentially reduce deviation
25        while max_heap[0] % 2 == 0:
26            largest_neg = heapq.heappop(max_heap)  # Pop the largest element
27            new_value = largest_neg // 2  # Halve it (dividing a negative number by 2 gives a smaller negative number)
28            heapq.heappush(max_heap, new_value)  # Push the new halved value back on the heap
29            min_value = min(min_value, -new_value)  # update min_value in regards to this new value
30            # Update the answer with the new smallest deviation possible
31            answer = min(answer, -max_heap[0] - min_value)
32      
33        # Once the largest value in the max_heap is odd, we can't make any more moves to reduce deviation.
34        return answer
35

1class Solution {
2    public int minimumDeviation(int[] nums) {
3        // Create a Priority Queue which sorts in descending order
4        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
5      
6        // Initialize minimum value to the largest possible integer
7        int minElement = Integer.MAX_VALUE;
8      
9        // Pre-process the array
10        for (int value : nums) {
11            // If the value is odd, multiply by 2 to convert it to even as the deviation operation.
12            if (value % 2 == 1) {
13                value <<= 1;
14            }
15            // Add the processed value to the queue
16            queue.offer(value);
17            // Update the minimum value encountered so far
18            minElement = Math.min(minElement, value);
19        }
20      
21        // Calculate the initial deviation
22        int deviation = queue.peek() - minElement;
23      
24        // While the largest element in the queue is even
25        while (queue.peek() % 2 == 0) {
26            // Divide the largest element by 2 (which is an allowed operation)
27            int topElement = queue.poll() / 2;
28          
29            // Add the reduced element back to the queue
30            queue.offer(topElement);
31          
32            // Update the minimum element after dividing the largest element
33            minElement = Math.min(minElement, topElement);
34          
35            // Update deviation if a smaller one is found
36            deviation = Math.min(deviation, queue.peek() - minElement);
37        }
38      
39        // Return the minimum deviation found
40        return deviation;
41    }
42}
43

1#include <queue>
2#include <vector>
3#include <climits> // for INT_MAX
4
5class Solution {
6public:
7    int minimumDeviation(vector<int>& nums) {
8        // Initialize the minimum found so far with the maximum possible integer value
9        int min_value = INT_MAX;
10
11        // Use a max priority queue to keep track of the current max value
12        priority_queue<int> max_queue;
13
14        // Preprocess the numbers in the initial vector
15        for (int value : nums) {
16            // If the number is odd, multiply it by 2 (to make it even)
17            if (value % 2 != 0) value *= 2;
18
19            // Push the possibly altered value onto the priority queue
20            max_queue.push(value);
21
22            // Update the minimum found so far
23            min_value = min(min_value, value);
24        }
25
26        // Calculate the initial deviation between the max value and the min_value
27        int deviation = max_queue.top() - min_value;
28
29        // While the maximum element in max_queue is even
30        while (max_queue.top() % 2 == 0) {
31            // Take the top (max) element and divide it by 2
32            int max_value = max_queue.top() / 2;
33
34            // Remove the top element from the priority queue
35            max_queue.pop();
36
37            // Push the new divided value back onto the priority queue
38            max_queue.push(max_value);
39
40            // Update the minimum value if necessary
41            min_value = min(min_value, max_value);
42
43            // Update the deviation between current max and the min_value
44            deviation = min(deviation, max_queue.top() - min_value);
45        }
46
47        // Return the minimum deviation found
48        return deviation;
49    }
50};
51

1// Import the necessary elements for the priority queue implementation
2import PriorityQueue from 'ts-priority-queue';
3
4function minimumDeviation(nums: number[]): number {
5    // Initialize the minimum found so far with the maximum safe integer value
6    let minValue: number = Number.MAX_SAFE_INTEGER;
7
8    // Use a max priority queue to keep track of the current max value
9    // Comparator function for max priority queue (reversing arguments for max behavior)
10    let maxQueue = new PriorityQueue<number>({
11        comparator: function(a, b) { return b - a; }
12    });
13
14    // Preprocess the numbers in the initial array
15    nums.forEach(value => {
16        // If the number is odd, multiply it by 2 (to make it even)
17        if (value % 2 !== 0) value *= 2;
18
19        // Push the possibly altered value onto the priority queue
20        maxQueue.queue(value);
21
22        // Update the minimum found so far
23        minValue = Math.min(minValue, value);
24    });
25
26    // Calculate the initial deviation between the max value and the minValue
27    let deviation: number = maxQueue.peek() - minValue;
28
29    // While the maximum element in maxQueue is even
30    while (maxQueue.peek() % 2 === 0) {
31        // Take the top (max) element and divide it by 2
32        let maxValue: number = maxQueue.dequeue() / 2;
33
34        // Push the new divided value back onto the priority queue
35        maxQueue.queue(maxValue);
36
37        // Update the minimum value if necessary
38        minValue = Math.min(minValue, maxValue);
39
40        // Update the deviation between current max and the minValue
41        deviation = Math.min(deviation, maxQueue.peek() - minValue);
42    }
43
44    // Return the minimum deviation found
45    return deviation;
46}
47

Time and Space Complexity

Time Complexity

The time complexity of the given code is determined by the following operations:

The loop that processes each element to identify if it's odd and to potentially double it, which runs in O(n), where n is the size of the input list nums.
The heapify operation on the list h which has a time complexity of O(n).
The while loop, which has a variable number of iterations depending on the values in the heap. In the worst case, each element may be divided by 2 until it becomes odd, which can happen at most log(max_element) times for each element. Since each iteration involves a heappop and heappush, both of which have O(log(n)) complexity, the total for this part is O(n * log(n) * log(max_element)).

Adding these up, we get:

Initial loop and heapify: O(2n) = O(n)
While loop: O(n * log(n) * log(max_element))

Since log(max_element) will be at most around 30 for integers within the 32-bit range, we can treat it as a constant factor, simplifying our worst-case time complexity to O(n * log(n)).

Space Complexity

The space complexity of the code is determined by the additional space used, which are:

The heap h, which contains at most n elements, so O(n).
The variable mi and other temporary variables, which use a fixed amount of space and thus can be considered O(1).

Therefore, the total space complexity is O(n) due to the heap.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don’t know