Skip to main content
Talentd

Minimize Deviation in Array - Solution & Explanation

HardArrayGreedyHeap (Priority Queue)Ordered Set22 min readAsked at: Samsung
Practice this problem

Problem Statement

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.

 

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 <= 5 * 104
  • 1 <= nums[i] <= 109

Approach Overview

Problem 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.

Approach 1: Approach using Max-Heap

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting operations on each iteration.
Space Complexity: O(n) for the heap structure representation.

Try this approach in the editor →

Approach 2: Approach using Dynamic Adjustment

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: 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.

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).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach using Max-Heap

Time Complexity: O(n log n) due to sorting operations on each iteration.
Space Complexity: O(n) for the heap structure representation.

Approach using Dynamic Adjustment

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.

Greedy + Priority Queue—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with Max-HeapO(n log n * log M)O(n)Best general solution. Efficiently reduces the current maximum using a priority queue.
Dynamic Adjustment with Ordered SetO(n log n * log M)O(n)Useful when using balanced BST or language libraries that provide ordered sets.

Video Solution

Minimize Deviation in Array - Leetcode 1675 - Python • NeetCodeIO • 15,294 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimize Deviation in Array easy or hard?
Minimize Deviation in Array is classified as a Hard problem on LeetCode. The difficulty comes from recognizing the normalization trick (doubling odd numbers first) and applying a greedy loop with a heap to gradually reduce the deviation.
Minimize Deviation in Array Python/Java solution
In Python, the solution typically uses the heapq module (with negated values to simulate a max-heap). Java implementations use PriorityQueue with a custom comparator for max behavior. Both follow the same greedy idea: normalize numbers, repeatedly halve the maximum, and track the minimum deviation.
How to solve Minimize Deviation in Array in O(n)?
A strict O(n) solution is not feasible because the algorithm needs repeated access to the current maximum element. Data structures such as a max-heap or ordered set are required, which introduce O(log n) operations. The practical optimal complexity is O(n log n * log M).
What is the best approach for Minimize Deviation in Array?
The best approach uses a greedy strategy with a max-heap (priority queue). First convert all odd numbers to even by multiplying them by 2, then repeatedly reduce the current maximum by dividing it by 2 while tracking the minimum value. This ensures the deviation shrinks whenever possible and runs in O(n log n * log M) time.
Is Minimize Deviation in Array asked at Google/Amazon/Meta?
Minimize Deviation in Array is a hard-level problem commonly discussed in interviews at companies like Google, Amazon, and Meta. It tests greedy reasoning, heap usage, and the ability to reason about value transformations in arrays.
What data structure is used in Minimize Deviation in Array?
The most common data structure is a max-heap (priority queue) to quickly access and update the largest element. Some implementations use an ordered set or balanced binary search tree to keep the array sorted while dynamically adjusting values.
What is the time complexity of Minimize Deviation in Array?
The optimal solution runs in O(n log n * log M) time, where n is the number of elements and M is the maximum value in the array. Each heap operation costs O(log n), and every element can be halved only a limited number of times (bounded by log M). Space complexity is O(n).

Ready to solve this problem?

Practice Minimize Deviation in Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays