Minimize deviation in array

Array Greedy Heap (Priority Queue) Ordered Set

54.0% acceptance

Feb 25, 2026

3086

175

You are given an array nums of n positive integers. Operations: if element is even, divide by 2; if odd, multiply by 2. The deviation is the maximum difference between any two elements. Return the minimum deviation after performing some operations.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::collections::BinaryHeap;

impl Solution {
  pub fn minimum_deviation(nums: Vec<i32>) -> i32 {
    // First, maximize all elements: odds * 2 (can only go up), evens stay
    let mut heap: BinaryHeap<i32> = BinaryHeap::new();
    let mut min_val = i32::MAX;
    for &n in &nums {
      let x = if n % 2 == 1 { n * 2 } else { n };
      heap.push(x);
      min_val = min_val.min(x);
    }
    // Repeatedly divide the maximum (even) by 2, tracking min deviation
    let mut ans = i32::MAX;
    loop {
      let max_val = *heap.peek().unwrap();
      let diff = max_val - min_val;
      ans = ans.min(diff);
      if max_val % 2 == 1 {
        break; // max is odd, can't divide further
      }
      heap.pop();
      let new_val = max_val / 2;
      min_val = min_val.min(new_val);
      heap.push(new_val);
    }
    ans
  }
}