# 1675. Minimize Deviation in Array (pq or TreeSet

## use **PriorityQueue**

T:  O(n \* logn\* logM); M is the largest number, **n** is length of nums , => logM is max 32 (32-bit int), which is treated as constant => so O(nlogn) is fine

S: O(m)

```java
class Solution {
    public int minimumDeviation(int[] nums) {
        Queue<Integer> pq = new PriorityQueue<>();
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num % 2 == 1) {
                num = 2*num;
            }
            pq.offer(-num);
            min = Math.min(min, num);
        }
        int res = Integer.MAX_VALUE;
        while (true) {
            int largget = -pq.poll();
            res = Math.min(res, largget - min);
            
            if (largget % 2 == 0) {
                min = Math.min(min, largget/2);
                pq.offer(-largget/2);
            } else {
                break;
            }
        }
        return res;
    }
}

/*
make max diff(deviation) minimized
*/
```

## use TreeSet

T:  O(n \* logn\* logM); M is the largest number, **n** is length of nums , => logM is max 32 (32-bit int), which is treated as constant => so O(nlogn) is fine

S: O(m)

```java
class Solution {
    public int minimumDeviation(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int num : nums) {
            if (num % 2 == 0) {
                set.add(num);
            } else {
                set.add(num*2);
            }
        }
        int res = Integer.MAX_VALUE;
        while (true) {
            int largget = set.last();
            res = Math.min(res, largget - set.first());
            
            if (largget % 2 == 0) {
                set.remove(largget);
                set.add(largget/2);
            } else {
                break;
            }
        }
        return res;
    }
}

/*
make max diff(deviation) minimized
*/
```