# Minimize Deviation in Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimize-deviation-in-array)
Canonical: https://scaleengineer.com/dsa/problems/minimize-deviation-in-array
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Heap (Priority Queue), Ordered Set
**Companies:** [Samsung](https://scaleengineer.com/companies/samsung)
---
## 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 * 104`
* `1 <= nums[i] <= 109`

# Approaches
## Brute Force with Backtracking
This approach explores every single possible configuration of the array. For each number in the input array, we first generate all the values it can be transformed into. Then, using recursion (backtracking), we try every combination of picking one value for each original number. For each complete combination, we compute its deviation and keep track of the minimum deviation seen across all combinations.
**Time:** O(Π |S_i|), where |S_i| is the number of possible values for `nums[i]`. Since |S_i| can be up to `O(log M)` where `M` is the value of the number, this complexity is exponential in `N` and thus not practical. · **Space:** O(N + T), where `N` is the number of elements and `T` is the total number of possible values across all elements. `O(N)` for the recursion stack depth and `O(T)` to store all possible values.
**Pros:** Conceptually simple and directly follows the problem definition.
**Cons:** Extremely inefficient and will time out on constraints specified in the problem.; The number of combinations grows exponentially with the number of elements `n`.
### Explanation
The brute-force method systematically generates all potential arrays that can be formed by applying the allowed operations. It's a straightforward translation of the problem statement but computationally infeasible for the given constraints.

```java
class Solution {
    int minDeviation = Integer.MAX_VALUE;
    java.util.List<java.util.List<Integer>> possibleValues;

    public int minimumDeviation(int[] nums) {
        possibleValues = new java.util.ArrayList<>();
        for (int num : nums) {
            java.util.Set<Integer> values = new java.util.HashSet<>();
            if (num % 2 == 1) {
                values.add(num);
                values.add(num * 2);
            } else {
                int current = num;
                while (current % 2 == 0) {
                    values.add(current);
                    current /= 2;
                }
                values.add(current);
            }
            possibleValues.add(new java.util.ArrayList<>(values));
        }
        
        backtrack(0, new java.util.ArrayList<>());
        return minDeviation;
    }

    private void backtrack(int index, java.util.List<Integer> currentCombination) {
        if (index == possibleValues.size()) {
            if (currentCombination.isEmpty()) return;
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            for (int val : currentCombination) {
                min = Math.min(min, val);
                max = Math.max(max, val);
            }
            minDeviation = Math.min(minDeviation, max - min);
            return;
        }

        for (int val : possibleValues.get(index)) {
            currentCombination.add(val);
            backtrack(index + 1, currentCombination);
            currentCombination.remove(currentCombination.size() - 1);
        }
    }
}
```
### Algorithm
1. For each number `nums[i]` in the input array, generate a list of all its possible values. An odd number `x` can become `x` or `2x`. An even number `y` can become any value in the sequence `y, y/2, y/4, ...` until it becomes odd.
2. Use a recursive backtracking function, say `findMinDeviation(index, currentCombination)`, to explore all possible arrays that can be formed.
3. The function takes the current index `index` to be filled and the `currentCombination` of numbers chosen so far.
4. **Base Case:** If `index` equals the length of the array, it means we have a complete combination. Calculate the deviation (`max - min`) for this combination and update the global minimum deviation found so far.
5. **Recursive Step:** For the number at `nums[index]`, iterate through all its possible values. For each possible value `v`, add it to the `currentCombination` and make a recursive call for the next index: `findMinDeviation(index + 1, currentCombination)`. Remember to backtrack by removing `v` after the recursive call returns.

## Sliding Window on Merged Lists
This approach reframes the problem as a well-known one: finding the smallest range that covers at least one element from each of `k` sorted lists. Here, our `k` lists are the sets of possible values for each number in the input `nums`. We merge all these possible values, sort them, and then use a sliding window to find the narrowest range that includes a value from each original number's set of possibilities.
**Time:** O(T log T), where `T = N * log M`. The complexity is dominated by sorting the merged list of all possible values. · **Space:** O(T), where `T` is the total number of possible values, which is `O(N * log M)`. This space is needed for the merged list.
**Pros:** Guaranteed to find the optimal solution.; Much more efficient than brute force.; It's a standard pattern for 'smallest range' problems.
**Cons:** Requires significant memory to store all possible values from all lists.; Time complexity is dominated by sorting a potentially large merged list.
### Explanation
This method is more structured than brute force. By transforming the problem, we can apply a standard algorithm.

```java
class Solution {
    public int minimumDeviation(int[] nums) {
        int n = nums.length;
        java.util.List<int[]> allValues = new java.util.ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            if (num % 2 == 1) {
                allValues.add(new int[]{num, i});
                allValues.add(new int[]{num * 2, i});
            } else {
                int current = num;
                while (current % 2 == 0) {
                    allValues.add(new int[]{current, i});
                    current /= 2;
                }
                allValues.add(new int[]{current, i});
            }
        }
        
        java.util.Collections.sort(allValues, (a, b) -> Integer.compare(a[0], b[0]));
        
        int minDeviation = Integer.MAX_VALUE;
        int left = 0;
        int[] counts = new int[n];
        int distinctCount = 0;
        
        for (int right = 0; right < allValues.size(); right++) {
            int[] rightElem = allValues.get(right);
            if (counts[rightElem[1]] == 0) {
                distinctCount++;
            }
            counts[rightElem[1]]++;
            
            while (distinctCount == n) {
                int[] leftElem = allValues.get(left);
                int currentDeviation = allValues.get(right)[0] - leftElem[0];
                minDeviation = Math.min(minDeviation, currentDeviation);
                
                counts[leftElem[1]]--;
                if (counts[leftElem[1]] == 0) {
                    distinctCount--;
                }
                left++;
            }
        }
        
        return minDeviation;
    }
}
```
### Algorithm
1. **Generate Value Lists:** For each number in `nums`, generate a list of all its possible values. Let's say we have `N` such lists.
2. **Merge and Sort:** Create a single master list containing all values from all `N` lists. Each element in this master list should be a pair `(value, original_list_index)`.
3. Sort this master list based on `value`.
4. **Sliding Window:** Use two pointers, `left` and `right`, to define a sliding window on the sorted master list. Maintain a frequency map (or an array `counts`) to track how many elements from each of the `N` original lists are currently inside the window.
5. **Expand Window:** Move the `right` pointer to expand the window. For each new element, update the `counts` for its `original_list_index`.
6. **Check Validity and Shrink:** Once the window contains at least one element from every original list (i.e., all `N` lists are represented), it's a valid candidate range. Calculate the deviation (`window_end_value - window_start_value`) and update the minimum deviation. Then, shrink the window from the left by moving the `left` pointer and updating the `counts` until the window is no longer valid. Repeat the expansion step.

## Greedy Approach with Max-Heap/TreeSet
This is the most efficient approach. The core idea is to eliminate one of the operations to simplify the problem. We observe that any number can be made even (by multiplying if odd). Once all numbers are even, we can only ever decrease them by dividing by 2. This transforms the problem into: given an array of even numbers, what's the minimum deviation we can achieve by repeatedly halving any element?

The greedy strategy is to always reduce the largest element. This is because reducing the largest element has the most potential to decrease the overall deviation (`max - min`). We use a max-heap or a sorted set to efficiently find and update the maximum element until it can no longer be reduced (i.e., it becomes odd).
**Time:** O(N * log(M) * log(N)). We insert `N` elements initially (`O(N log N)`). The main loop runs for a total of `O(N * log M)` divisions across all numbers, with each division involving heap/set operations costing `O(log N)`. · **Space:** O(N), to store the `N` numbers in the `TreeSet` or a priority queue.
**Pros:** Most efficient solution in both time and space.; The logic is streamlined by simplifying the operations.; Clean implementation using a sorted set or priority queue.
**Cons:** The greedy logic might not be immediately intuitive.
### Explanation
This greedy approach is both elegant and efficient. By ensuring all numbers start at their maximum potential (within the rules), we only need to consider decreasing values, which simplifies the state space we need to explore.

Using a `TreeSet` makes the implementation clean as it handles sorting and gives access to min/max elements in `O(log N)` time.

```java
import java.util.TreeSet;

class Solution {
    public int minimumDeviation(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>();
        
        // Pre-process the array to make all numbers even and at their max potential
        for (int num : nums) {
            if (num % 2 == 1) {
                set.add(num * 2);
            } else {
                set.add(num);
            }
        }
        
        int minDeviation = set.last() - set.first();
        
        // Greedily reduce the max element as long as it's even
        while (true) {
            int maxVal = set.last(); // Get the current maximum
            
            if (maxVal % 2 != 0) {
                // If max is odd, we can't reduce it further. Stop.
                break;
            }
            
            // Remove the max, halve it, and add it back
            set.remove(maxVal);
            set.add(maxVal / 2);
            
            // Update the minimum deviation found so far
            minDeviation = Math.min(minDeviation, set.last() - set.first());
        }
        
        return minDeviation;
    }
}
```
### Algorithm
1. **Normalize Initial Array:** The key insight is to simplify the available operations. Any number can be made even. An odd number `x` can be multiplied by 2. An even number is already even. Let's start by making every number as large as possible. We can do this by multiplying any odd number by 2. After this, all numbers are even, and the only operation we can perform is dividing by 2.
2. **Use a Max-Heap (or a Sorted Set):** Insert all the processed numbers into a data structure that can efficiently provide the minimum and maximum elements. A `TreeSet` in Java is perfect for this, as it keeps elements sorted.
3. **Initialize Deviation:** Calculate the initial deviation, which is `max_element - min_element` from the `TreeSet`.
4. **Greedy Reduction:** Start a loop. In each iteration:
   a. Extract the maximum element from the set.
   b. If this maximum element is odd, we cannot reduce it further. Since we are always targeting the largest value, no other operation can reduce the current deviation. So, we break the loop.
   c. If the maximum element is even, divide it by 2 and insert the new value back into the set.
   d. After updating the set, calculate the new deviation (`new_max - new_min`) and update our overall `minDeviation` if the new one is smaller.
5. **Return Result:** The loop terminates when the maximum element is odd. The `minDeviation` found holds the answer.

# Solutions
### Java

```java
class Solution {
public
  int minimumDeviation(int[] nums) {
    PriorityQueue<Integer> q = new PriorityQueue<>((a, b)->b - a);
    int mi = Integer.MAX_VALUE;
    for (int v : nums) {
      if (v % 2 == 1) {
        v <<= 1;
      }
      q.offer(v);
      mi = Math.min(mi, v);
    }
    int ans = q.peek() - mi;
    while (q.peek() % 2 == 0) {
      int x = q.poll() / 2;
      q.offer(x);
      mi = Math.min(mi, x);
      ans = Math.min(ans, q.peek() - mi);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumDeviation(vector<int> &nums) {
    int mi = INT_MAX;
    priority_queue<int> pq;
    for (int v : nums) {
      if (v & 1)
        v <<= 1;
      pq.push(v);
      mi = min(mi, v);
    }
    int ans = pq.top() - mi;
    while (pq.top() % 2 == 0) {
      int x = pq.top() >> 1;
      pq.pop();
      pq.push(x);
      mi = min(mi, x);
      ans = min(ans, pq.top() - mi);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minimumDeviation(self, nums: List[int]) -> int: h = [] mi = inf for v in nums: if v & 1: v <<= 1 h . append(- v) mi = min(mi, v) heapify(h) ans = - h[0] - mi while h[0] % 2 == 0: x = heappop(h) // 2 heappush(h, x) mi = min(mi, - x) ans = min(ans, - h[0] - mi) return ans

```