> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Minimize Deviation in Array Python Solution

> Tested Python solution for LeetCode 1675 with 45 pytest cases. Generate a practice environment with lcpy.

LeetCode 1675, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Greedy](/catalog/topics/greedy), [Heap (Priority Queue)](/catalog/topics/heap-priority-queue), [Ordered Set](/catalog/topics/ordered-set). [View on LeetCode](https://leetcode.com/problems/minimize-deviation-in-array/description/).

Generate this problem as a practice environment: tested reference solution, 45 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1675   # by problem number
lcpy gen -s minimize_deviation_in_array   # by problem name
```

## 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*.

### Examples

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

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

```
Input: nums = [2,10,8]
Output: 3
```

### Constraints

* n == nums.length
* 2 \<= n \<= 5 \* 10^4
* 1 \<= nums\[i] \<= 10^9

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimize_deviation_in_array/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimize_deviation_in_array/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import heapq


class Solution:
    # Time: O(n * log(max(nums)) * log n)
    # Space: O(n)
    def minimum_deviation(self, nums: list[int]) -> int:
        # Raise every element to its largest reachable form (an odd x can only
        # grow once, to 2x); then repeatedly shrink the current max while it is
        # even, tracking the tightest window seen.
        heap: list[int] = []
        low = 1 << 62
        for num in nums:
            value = num * 2 if num % 2 else num
            heapq.heappush(heap, -value)
            low = min(low, value)

        best = 1 << 62
        while True:
            high = -heapq.heappop(heap)
            best = min(best, high - low)
            if high % 2:
                break
            half = high // 2
            low = min(low, half)
            heapq.heappush(heap, -half)
        return best
```

## Complexity

| Time | Space |
| - | - |
| O(n \* log(max(nums)) \* log n) | O(n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.