1675. Minimize Deviation in Array LeetCode Solution

In this guide, you will get 1675. Minimize Deviation in Array LeetCode Solution with the best time and space complexity. The solution to Minimize Deviation in Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimize Deviation in Array solution in C++
Minimize Deviation in Array solution in Java
Minimize Deviation in Array solution in Python
Additional Resources

1675. Minimize Deviation in Array LeetCode Solution image

Problem Statement of Minimize Deviation in Array

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

Complexity Analysis

Time Complexity: O(\log\max(\texttt{nums}) \cdot n\log n)
Space Complexity: O(n)

1675. Minimize Deviation in Array LeetCode Solution in C++

class Solution {
 public:
  int minimumDeviation(vector<int>& nums) {
    int ans = INT_MAX;
    int mn = INT_MAX;
    priority_queue<int> maxHeap;

    for (const int num : nums) {
      const int evenNum = num % 2 == 0 ? num : num * 2;
      mn = min(mn, evenNum);
      maxHeap.push(evenNum);
    }

    while (maxHeap.top() % 2 == 0) {
      const int mx = maxHeap.top();
      maxHeap.pop();
      ans = min(ans, mx - mn);
      mn = min(mn, mx / 2);
      maxHeap.push(mx / 2);
    }

    return min(ans, maxHeap.top() - mn);
  }
};
/* code provided by PROGIEZ */

1675. Minimize Deviation in Array LeetCode Solution in Java

class Solution {
  public int minimumDeviation(int[] nums) {
    int ans = Integer.MAX_VALUE;
    int mn = Integer.MAX_VALUE;
    Queue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

    for (final int num : nums) {
      final int evenNum = num % 2 == 0 ? num : num * 2;
      mn = Math.min(mn, evenNum);
      maxHeap.offer(evenNum);
    }

    while (maxHeap.peek() % 2 == 0) {
      final int mx = maxHeap.poll();
      ans = Math.min(ans, mx - mn);
      mn = Math.min(mn, mx / 2);
      maxHeap.offer(mx / 2);
    }

    return Math.min(ans, maxHeap.peek() - mn);
  }
}
// code provided by PROGIEZ

1675. Minimize Deviation in Array LeetCode Solution in Python

class Solution:
  def minimumDeviation(self, nums: list[int]) -> int:
    ans = math.inf
    mn = math.inf
    maxHeap = []

    for num in nums:
      evenNum = num if num % 2 == 0 else num * 2
      heapq.heappush(maxHeap, -evenNum)
      mn = min(mn, evenNum)

    while maxHeap[0] % 2 == 0:
      mx = -heapq.heappop(maxHeap)
      ans = min(ans, mx - mn)
      mn = min(mn, mx // 2)
      heapq.heappush(maxHeap, -mx // 2)

    return min(ans, -maxHeap[0] - mn)
 # code by PROGIEZ