LeetCode 1675 - Minimize Deviation in Array

The problem asks us to minimize the deviation in an array of positive integers. The deviation is defined as the differen

leetcodehardarraygreedyheap-(priority-queue)ordered-set

LeetCode Problem 1675

Difficulty: 🔴 Hard
Topics: Array, Greedy, Heap (Priority Queue), Ordered Set

Solution

Problem Understanding

The problem asks us to minimize the deviation in an array of positive integers. The deviation is defined as the difference between the maximum and minimum elements in the array. We can modify the array using two operations: if an element is even, we can divide it by 2, and if an element is odd, we can multiply it by 2. Both operations can be applied any number of times to any element.

The input nums is an array of positive integers, and the output should be a single integer representing the minimum deviation possible after performing a sequence of allowed operations. The constraints indicate that the array can be large, up to 50,000 elements, and elements themselves can be up to 10^9. This means any naive brute-force approach that explores all possible sequences of operations will be infeasible due to exponential growth.

Edge cases to consider include arrays where all elements are already equal, arrays where all elements are odd or even, and arrays with a mix of very small and very large numbers. The problem guarantees at least two elements and all positive integers, so we do not need to handle empty arrays or zero/negative numbers.

Approaches

A brute-force approach would attempt to explore every sequence of operations on every element to track the minimum possible deviation. While correct in theory, this approach is too slow because the number of possible sequences grows exponentially with the array size and element values. It is not feasible given the constraints.

The key insight for an optimal solution is that the deviation is determined by the current maximum and minimum elements. Since even numbers can only decrease and odd numbers can only increase, we should first normalize the array by making every element even. This ensures that each element can then only decrease. Using a max-heap, we repeatedly reduce the largest element (if it is even) and track the minimum element in the heap. By doing this, we iteratively decrease the maximum while maintaining the current minimum, updating the deviation at each step. The process stops when the maximum is odd (cannot be reduced further), ensuring the smallest possible deviation is achieved.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n) Explore all sequences of operations; impractical for large n
Optimal O(n log n) O(n) Normalize all numbers to even, use max-heap to minimize deviation iteratively

Algorithm Walkthrough

  1. Iterate through the array nums. For each element, if it is odd, multiply it by 2. This ensures that all elements are even, which allows us to only reduce elements from this point onward.
  2. Initialize a max-heap. In Python, use a min-heap with negated values because the standard library provides only a min-heap.
  3. Track the minimum element in the array during the initial transformation, as this sets the baseline for computing deviation.
  4. While the heap is not empty, extract the maximum element from the heap (negating the value in Python). Compute the current deviation as the difference between this maximum and the tracked minimum, and update the result if it is smaller.
  5. If the maximum element is even, divide it by 2, update the minimum if necessary, and push it back into the heap. This simulates reducing the maximum while potentially reducing the overall deviation.
  6. If the maximum element is odd, break the loop, as it can no longer be reduced.
  7. Return the smallest deviation tracked.

Why it works: The algorithm ensures that we always reduce the current maximum element while tracking the current minimum. Since every element has been made even initially, all elements can only decrease, and this greedy reduction of the maximum guarantees that we explore all deviations that could lead to the minimum.

Python Solution

from typing import List
import heapq

class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        max_heap = []
        minimum = float('inf')
        
        for num in nums:
            if num % 2 == 1:
                num *= 2
            heapq.heappush(max_heap, -num)
            minimum = min(minimum, num)
        
        min_deviation = float('inf')
        
        while True:
            maximum = -heapq.heappop(max_heap)
            min_deviation = min(min_deviation, maximum - minimum)
            
            if maximum % 2 == 0:
                maximum //= 2
                minimum = min(minimum, maximum)
                heapq.heappush(max_heap, -maximum)
            else:
                break
        
        return min_deviation

The implementation begins by normalizing the array to ensure all elements are even. Each element is then pushed into a max-heap (as a negated number). The minimum element is tracked throughout to calculate the deviation at each step. The loop continues reducing the maximum until it becomes odd. The algorithm correctly returns the minimum deviation.

Go Solution

package main

import (
	"container/heap"
	"math"
)

type MaxHeap []int

func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any)         { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() any {
	n := len(*h)
	x := (*h)[n-1]
	*h = (*h)[:n-1]
	return x
}

func minimumDeviation(nums []int) int {
	h := &MaxHeap{}
	heap.Init(h)
	minimum := math.MaxInt32

	for _, num := range nums {
		if num%2 == 1 {
			num *= 2
		}
		heap.Push(h, num)
		if num < minimum {
			minimum = num
		}
	}

	minDeviation := math.MaxInt32

	for {
		maximum := heap.Pop(h).(int)
		if maximum-minimum < minDeviation {
			minDeviation = maximum - minimum
		}

		if maximum%2 == 0 {
			maximum /= 2
			if maximum < minimum {
				minimum = maximum
			}
			heap.Push(h, maximum)
		} else {
			break
		}
	}

	return minDeviation
}

In Go, we define a custom MaxHeap type to use the heap package for a max-heap. Otherwise, the logic mirrors the Python implementation: normalize the numbers, push to heap, track minimum, iteratively reduce maximum, and return the smallest deviation.

Worked Examples

Example 1: nums = [1,2,3,4]

Step Heap State (max first) Minimum Current Deviation Action
Initial [4, 2, 6, 2] 1 3 Push all, normalize odd numbers
1 [4,2,6,2] 1 5 (6-1) Pop 6, divide by 2 → 3, push 3
2 [4,3,2,2] 1 3 Pop 4, divide by 2 → 2, push 2
3 [3,2,2,2] 1 2 Pop 3, odd → stop

Minimum deviation = 1.

Example 2: nums = [4,1,5,20,3]

Normalization: [4,2,10,20,6]

Process by reducing maximums iteratively: final minimum deviation = 3.

Example 3: nums = [2,10,8]

Normalization: [2,10,8] (all even)

Reduce maximum 10 → 5 → 5 odd → stop

Deviation tracked → 3.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Each element may be halved at most log(max_num) times; heap operations cost O(log n) each
Space O(n) Max-heap stores all n elements

The reasoning is that each element can only be halved log2(max(nums)) times, and heap operations dominate the running time. Space is linear because we store all elements in a heap.

Test Cases

# provided examples
assert Solution().minimumDeviation([1,2,3,4]) == 1
assert Solution().minimumDeviation([4,1,5,20,3]) == 3
assert Solution().minimumDeviation([2,10,8]) == 3

# boundary tests
assert Solution().minimumDeviation([1,1]) == 0  # all equal
assert Solution().minimumDeviation([1,1000000000]) == 1  # extreme values
assert Solution().minimumDeviation([5,5,5,5]) == 0  # identical odd numbers
assert Solution().minimumDeviation([2,2,2,2]) == 0  # identical even numbers

# mixed large and small numbers
assert Solution().minimumDeviation([1,2,3,4,5,6,7,8,9,10]) == 1
Test Why
[1,2,3,4] Example with mixed odd/even numbers
[4,1,5,20,3]