1675. Minimize Deviation in Array Solution

Q: 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.

Q: 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.

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

Q: 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.

Q: 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.

Q: 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.

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

The problem

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 * 10⁴
1 <= nums[i] <= 10⁹

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.

Python

import heapq

class Solution:
    def minimumDeviation(self, nums):
        heap = []
        min_val = float('inf')

        for num in nums:
            if num % 2:
                num *= 2
            heapq.heappush(heap, -num)  # Python min-heap inverts the number to simulate a max-heap
            min_val = min(min_val, num)

        min_deviation = float('inf')

        while heap:
            max_val = -heapq.heappop(heap)
            min_deviation = min(min_deviation, max_val - min_val)
            if max_val % 2:
                break
            max_val //= 2
            min_val = min(min_val, max_val)
            heapq.heappush(heap, -max_val)

        return min_deviation

Java

import java.util.*;

public class MinimumDeviation {
    public int minimumDeviation(int[] nums) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        int minVal = Integer.MAX_VALUE;

        for (int num : nums) {
            if (num % 2 == 1) num *= 2; 
            minVal = Math.min(minVal, num);
            maxHeap.add(num);
        }

        int minDevi = Integer.MAX_VALUE;

        while (true) {
            int maxVal = maxHeap.poll();
            minDevi = Math.min(minDevi, maxVal - minVal);
            if (maxVal % 2 == 1) break;
            maxVal /= 2;
            minVal = Math.min(minVal, maxVal);
            maxHeap.add(maxVal);
        }

        return minDevi;
    }
}

C++

#include <iostream>
#include <queue>
#include <vector>
#include <climits>

using namespace std;

int minimumDeviation(vector<int>& nums) {
    priority_queue<int> maxHeap;
    int minVal = INT_MAX;

    for (int num : nums) {
        if (num % 2) num *= 2;
        maxHeap.push(num);
        if (num < minVal) minVal = num;
    }

    int minDeviation = INT_MAX;
    while (true) {
        int maxVal = maxHeap.top();
        maxHeap.pop();
        minDeviation = min(minDeviation, maxVal - minVal);
        if (maxVal % 2) break;

        maxVal /= 2;
        maxHeap.push(maxVal);
        if (maxVal < minVal) minVal = maxVal;
    }
    return minDeviation;
}

JavaScript

function minimumDeviation(nums) {
    const maxHeap = new MaxPriorityQueue();
    let minVal = Infinity;

    for (let num of nums) {
        if (num % 2 === 1) num *= 2;
        minVal = Math.min(minVal, num);
        maxHeap.enqueue(num);
    }

    let minDeviation = Infinity;

    while (maxHeap.size() > 0) {
        let maxVal = maxHeap.dequeue().element;
        minDeviation = Math.min(minDeviation, maxVal - minVal);
        if (maxVal % 2 === 1) break;
        maxVal = Math.floor(maxVal / 2);
        minVal = Math.min(minVal, maxVal);
        maxHeap.enqueue(maxVal);
    }

    return minDeviation;
}

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return *(int*)b - *(int*)a;
}

int minimumDeviation(int* nums, int numsSize){
    int min_val = INT_MAX;
    int* heap = (int*)malloc(sizeof(int) * numsSize * 2);
    int heapSize = 0;

    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] % 2 == 1) nums[i] *= 2;
        min_val = nums[i] < min_val ? nums[i] : min_val;
        heap[heapSize++] = nums[i];
    }

    qsort(heap, heapSize, sizeof(int), compare);

    int min_deviation = INT_MAX;

    while (1) {
        int max_val = heap[0];
        min_deviation = min_deviation < (max_val - min_val) ? min_deviation : (max_val - min_val);
        if (max_val % 2 == 1) break;
        max_val /= 2;
        min_val = min_val < max_val ? min_val : max_val;

        heap[0] = max_val;
        qsort(heap, heapSize, sizeof(int), compare);
    }

    free(heap);
    return min_deviation;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int MinimumDeviation(int[] nums) {
        PriorityQueue<int, int> maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));
        int minVal = int.MaxValue;

        foreach (var num in nums) {
            var newValue = num % 2 == 1 ? num * 2 : num;
            minVal = Math.Min(minVal, newValue);
            maxHeap.Enqueue(newValue, newValue);
        }

        int minDeviation = int.MaxValue;

        while (maxHeap.Count > 0) {
            int maxVal = maxHeap.Dequeue();
            minDeviation = Math.Min(minDeviation, maxVal - minVal);
            if (maxVal % 2 == 1) break;
            maxVal /= 2;
            minVal = Math.Min(minVal, maxVal);
            maxHeap.Enqueue(maxVal, maxVal);
        }

        return minDeviation;
    }
}

The Python approach uses the heapq module to construct a max-heap by inversing values (using negation).

It iteratively removes the highest number, adjusts its value, and manages updates of the deviation/minimum value each cycle.

Complexity

Time Complexity: O(n log n) based on heap operations.
Space Complexity: O(n) for heap storage.

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.

Python

class Solution:
    def minimumDeviation(self, nums):
        nums = [num * 2 if num % 2 else num for num in nums]
        nums.sort()
        min_deviation = nums[-1] - nums[0]

        while nums[-1] % 2 == 0:
            nums[-1] //= 2
            nums.sort()
            min_deviation = min(min_deviation, nums[-1] - nums[0])

        return min_deviation

Java

import java.util.*;

public class MinimumDeviation {
    public int minimumDeviation(int[] nums) {
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] % 2 == 1) nums[i] *= 2;
        }
        Arrays.sort(nums);
        int minDeviation = nums[nums.length - 1] - nums[0];

        while (nums[nums.length - 1] % 2 == 0) {
            nums[nums.length - 1] /= 2;
            Arrays.sort(nums);
            minDeviation = Math.min(minDeviation, nums[nums.length - 1] - nums[0]);
        }

        return minDeviation;
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int minimumDeviation(vector<int>& nums) {
    for (auto &num : nums)
        if (num % 2 == 1) num *= 2;

    sort(nums.begin(), nums.end());
    int minDeviation = nums.back() - nums.front();

    while (nums.back() % 2 == 0) {
        nums.back() /= 2;
        sort(nums.begin(), nums.end());
        minDeviation = min(minDeviation, nums.back() - nums.front());
    }

    return minDeviation;
}

JavaScript

function minimumDeviation(nums) {
    nums = nums.map(num => num % 2 === 1 ? num * 2 : num);
    nums.sort((a, b) => a - b);
    let minDeviation = nums[nums.length - 1] - nums[0];

    while (nums[nums.length - 1] % 2 === 0) {
        nums[nums.length - 1] /= 2;
        nums.sort((a, b) => a - b);
        minDeviation = Math.min(minDeviation, nums[nums.length - 1] - nums[0]);
    }

    return minDeviation;
}

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int minimumDeviation(int* nums, int numsSize){
    for (int i=0; i < numsSize; i++) {
        if (nums[i] % 2 == 1) nums[i] *= 2;
    }
    qsort(nums, numsSize, sizeof(int), compare);

    int min_deviation = nums[numsSize - 1] - nums[0];
    int maxVal = nums[numsSize - 1];
    while (maxVal % 2 == 0) {
        maxVal /= 2;
        nums[numsSize - 1] = maxVal;
        qsort(nums, numsSize, sizeof(int), compare);
        min_deviation = min_deviation < (nums[numsSize - 1] - nums[0]) ? min_deviation : (nums[numsSize - 1] - nums[0]);
    }
    return min_deviation;
}

using System;
using System.Linq;

public class Solution {
    public int MinimumDeviation(int[] nums) {
        nums = nums.Select(num => num % 2 == 1 ? num * 2 : num).ToArray();
        Array.Sort(nums);
        int minDeviation = nums.Last() - nums.First();

        while (nums[nums.Length - 1] % 2 == 0) {
            nums[nums.Length - 1] /= 2;
            Array.Sort(nums);
            minDeviation = Math.Min(minDeviation, nums[nums.Length - 1] - nums[0]);
        }

        return minDeviation;
    }
}

Python follows an approach where the focus is on list alterations and sorting with winterations on present list max reduction. Implementation favors simpler ideas of deviation minimization in sorted contexts.

Complexity

Time Complexity: O(n^2 log n) due multiple list sortings.
Space Complexity: O(n) based on list manipulation needs.

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

func minimumDeviation(nums []int) int {
	q := hp{}
	mi := math.MaxInt32
	for _, v := range nums {
		if v%2 == 1 {
			v <<= 1
		}
		heap.Push(&q, v)
		mi = min(mi, v)
	}
	ans := q.IntSlice[0] - mi
	for q.IntSlice[0]%2 == 0 {
		x := heap.Pop(&q).(int) >> 1
		heap.Push(&q, x)
		mi = min(mi, x)
		ans = min(ans, q.IntSlice[0]-mi)
	}
	return ans
}

type hp struct{ sort.IntSlice }

func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
	a := h.IntSlice
	v := a[len(a)-1]
	h.IntSlice = a[:len(a)-1]
	return v
}
func (h *hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach using Max-Heap	Time Complexity: O(n log n) based on heap operations. Space Complexity: O(n) for heap storage.
Approach using Dynamic Adjustment	Time Complexity: O(n^2 log n) due multiple list sortings. Space Complexity: O(n) based on list manipulation needs.
Greedy + Priority Queue	–

Complexity analysis

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.

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

Minimize Deviation in Array solution and explanation

The problem

Approach overview

Approach 1: Approach using Max-Heap

Approach 2: Approach using Dynamic Adjustment

Approach 3: Greedy + Priority Queue

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimize Deviation in Array solution and explanation

The problem

Approach overview

Approach 1: Approach using Max-Heap

Approach 2: Approach using Dynamic Adjustment

Approach 3: Greedy + Priority Queue

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems