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:
2.
[1,2,3,4], then you can do this operation on the last element, and the array will be [1,2,3,2].2.
[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.
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.length2 <= n <= 5 * 1041 <= nums[i] <= 109Problem 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.
This approach utilizes a max-heap to efficiently retrieve the largest element while adjusting it within the array to reduce deviation.
1. First, we convert all numbers to even (since an odd number can only become larger when even via multiplication). This is done by multiplying odd numbers by 2.
2. We utilize a max-heap where each iteration involves reducing the maximum number (if even) to reduce the deviation.
3. Throughout this process, track the minimum seen number to calculate and update the minimum deviation at every stage.
The core idea is to use sorting as a form of managing the max-heap. We multiply each odd by 2 and maintain an array. Sort it to effectively manage the largest element.
The element changes are managed in situ over each comparison step, reducing the maximum each time by half if it's even and updating the reference minimum.
Time Complexity: O(n log n) due to sorting operations on each iteration.
Space Complexity: O(n) for the heap structure representation.
In this alternative approach, the strategy focuses on an incremental adjustment instead of heap reliance. It involves directly mutating and managing the adjustment in a sorted sequence approach to target deviation reduction without standard heap operations.
1. First, transform any odd number by doubling it. Track the preliminary minimum number.
2. Sort the array and iteratively adjust the maximum through division by halving until reaching an odd number.
The minimum deviation is kept through direct comparison evaluations across the deviations achieved after each max adjustment.
The solution involves a sorting and comparison dynamic without direct priority queue adjustments. Key effect revolves around a sorted list whereby operations are performed directly, sorting on each maximum reduction progress.
Time Complexity: O(n^2 log n) due to multiple sorts.
Space Complexity: O(1) or O(n) considering in-place sorts might not require extra space.
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.
Since there are two operations that can be performed each time: multiply an odd number by 2; divide an even number by 2, the situation is more complex. We can multiply all odd numbers by 2 to convert them into even numbers, which is equivalent to having only one division operation. The division operation can only reduce a certain number, and only by reducing the maximum value can the result be more optimal.
Therefore, we use a priority queue (max heap) to maintain the maximum value of the array. Each time we take out the top element of the heap for division operation, put the new value into the heap, and update the minimum value and the minimum value of the difference between the top element of the heap and the minimum value.
When the top element of the heap is an odd number, the operation stops.
The time complexity is O(nlog n times log m). Where n and m are the length of the array nums and the maximum element of the array, respectively. Since the maximum element in the array is divided by 2 at most O(log m) times, all elements are divided by 2 at most O(nlog m) times. Each time the heap is popped and put into operation, the time complexity is O(log n). Therefore, the total time complexity is O(nlog n times log m).
| Approach | Complexity |
|---|---|
| Approach using Max-Heap | Time Complexity: O(n log n) due to sorting operations on each iteration. |
| Approach using Dynamic Adjustment | Time Complexity: O(n^2 log n) due to multiple sorts. |
| Greedy + Priority Queue | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Max-Heap | O(n log n * log M) | O(n) | Best general solution. Efficiently reduces the current maximum using a priority queue. |
| Dynamic Adjustment with Ordered Set | O(n log n * log M) | O(n) | Useful when using balanced BST or language libraries that provide ordered sets. |
Minimize Deviation in Array - Leetcode 1675 - Python • NeetCodeIO • 14,883 views views
Watch 9 more video solutions →Practice Minimize Deviation in Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor