Minimum cost to make array equal

Array Binary Search Greedy Sorting Prefix Sum

46.7% acceptance

Feb 25, 2026

2518

You are given two 0-indexed arrays nums and cost consisting each of n positiv e integers. * You can do the following operation any number of times: Increase or decrease any element of the array nums by 1. The cost of doing one operation on the ith element is cost[i]. Return the minimum total cost such that all the elements of the array nums be come equal. *

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost(nums: Vec<i32>, cost: Vec<i32>) -> i64 {
    let mut pairs: Vec<(i32, i64)> = nums.iter().zip(cost.iter()).map(|(&x, &c)| (x, c as i64)).collect();
    pairs.sort();
    let total: i64 = pairs.iter().map(|&(_, c)| c).sum();
    let half = total / 2;
    // weighted median: find target where prefix cost >= half
    let mut prefix = 0i64;
    let mut target = pairs[0].0;
    for &(x, c) in &pairs {
      prefix += c;
      target = x;
      if prefix > half { break; }
    }
    // compute cost at target
    pairs.iter().map(|&(x, c)| (x as i64 - target as i64).abs() * c).sum()
  }
}