Minimize Deviation in Array

LeetCode 1794 | Difficulty: Hard

Hard

Problem Description

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

- `1 <= nums[i] <= 10^9`

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

---

Approach

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

---

Solutions

Solution 1: C# (Best: 825 ms)

Metric	Value
Runtime	825 ms
Memory	57.6 MB
Date	2022-02-20

Solution

public class Solution {
    public int MinimumDeviation(int[] nums) {
        SortedSet<int> vals = new SortedSet<int>(Comparer<int>.Create((x, y) => y.CompareTo(x)));
    int min = Int32.MaxValue;
    int result = Int32.MaxValue;
    foreach (var num in nums)
    {
        int toAdd = num % 2 == 0 ? num : num * 2;
        vals.Add(toAdd);
        min = Math.Min(min, toAdd);
    }
    while (vals.Count != 0)
    {
        int max = vals.First();
        result = Math.Min(result, max - min);
        if(max%2 == 1) break;
        min = Math.Min(min,max/2);
        vals.Remove(max);
        vals.Add(max / 2);
    }


    return result;
    }
}

📜 2 more C# submission(s)

Submission (2022-02-20) — 855 ms, 57 MB

public class Solution {
    public int MinimumDeviation(int[] nums) {
        SortedSet<int> vals = new SortedSet<int>(Comparer<int>.Create((x, y) => y.CompareTo(x)));
    int min = Int32.MaxValue;
    int result = Int32.MaxValue;
    foreach (var num in nums)
    {
        int toAdd = num % 2 == 0 ? num : num * 2;
        vals.Add(toAdd);
        min = Math.Min(min, toAdd);
    }
    while (vals.Count != 0)
    {
        int max = vals.First();
        result = Math.Min(result, vals.First() - min);
        if(max%2 == 1) break;
        min = Math.Min(min,max/2);
        vals.Remove(max);
        vals.Add(max / 2);
    }


    return result;
    }
}

Submission (2022-02-20) — 1047 ms, 57.7 MB

public class Solution {
    public int MinimumDeviation(int[] nums) {
        PriorityQueue<int> vals = new PriorityQueue<int>(Comparer<int>.Create((x, y) => y.CompareTo(x)));
    int min = Int32.MaxValue;
    int result = Int32.MaxValue;
    foreach (var num in nums)
    {
        int toAdd = num % 2 == 0 ? num : num * 2;
        vals.Enqueue(toAdd);
        min = Math.Min(min, toAdd);
    }
    while (vals.Count() != 0)
    {
        int max = vals.Dequeue();
        result = Math.Min(result, max - min);
        if(max%2 == 1)
        {
            break;
        }
        else
        {
            min = Math.Min(min, max / 2);
            vals.Enqueue(max / 2);
        }
    }

    return result;
    }
}

public class PriorityQueue<T> where T : IComparable<T>
{
    public SortedDictionary<T, int> data;
    public int size = 0;
    private readonly int? capacity;

    public PriorityQueue(int? capacity = null)
    {
        this.data = new SortedDictionary<T, int>();
        this.capacity = capacity;
    }

    public PriorityQueue(IComparer<T> comparer, int? capacity = null)
    {
        this.data = new SortedDictionary<T, int>(comparer);
        this.capacity = capacity;
    }

    public void Enqueue(T item)
    {
        if (capacity.HasValue && capacity == size) Dequeue();
        if (data.ContainsKey(item))
        {
            data[item]++;
        }
        else
        {
            data.Add(item, 1);
        }
        size++;
    }

    public T Dequeue()
    {
        var front = data.First();
        if (front.Value == 1) data.Remove(front.Key);
        else data[front.Key]--;
        size--;
        return front.Key;
    }

    public bool Contains(T item)
    {
        return data.ContainsKey(item);
    }

    public void Remove(T item)
    {
        if (data[item] == 1) data.Remove(item);
        else data[item]--;
        size--;
    }

    public T Peek()
    {
        return data.First().Key;
    }

    public int Count()
    {
        return size;
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Assume you start with the minimum possible value for each number so you can only multiply a number by 2 till it reaches its maximum possible value.

Hint 2: If there is a better solution than the current one, then it must have either its maximum value less than the current maximum value, or the minimum value larger than the current minimum value.

Hint 3: Since that we only increase numbers (multiply them by 2), we cannot decrease the current maximum value, so we must multiply the current minimum number by 2.