Minimum Cost to Make Array Equal
Problem
You are given two integer arrays nums and cost of the same length. You may pick any target value and raise or lower each nums[i] until every element equals that target. Changing nums[i] by 1 (up or down) costs cost[i] each step, so moving it all the way to the target costs cost[i] · |nums[i] − target|. Return the minimum total cost to make all elements equal.
nums = [1, 3, 5, 2], cost = [2, 3, 1, 14]8def min_cost(nums, cost):
pairs = sorted(zip(nums, cost))
total = sum(cost)
half = total / 2
acc = 0
target = pairs[0][0]
for value, weight in pairs:
acc += weight
if acc >= half:
target = value
break
ans = 0
for n, c in zip(nums, cost):
ans += c * abs(n - target)
return ansfunction minCost(nums, cost) {
const pairs = nums.map((v, i) => [v, cost[i]]);
pairs.sort((a, b) => a[0] - b[0]);
let total = 0;
for (const c of cost) total += c;
const half = total / 2;
let acc = 0, target = pairs[0][0];
for (const [value, weight] of pairs) {
acc += weight;
if (acc >= half) { target = value; break; }
}
let ans = 0;
for (let i = 0; i < nums.length; i++) ans += cost[i] * Math.abs(nums[i] - target);
return ans;
}class Solution {
public long minCost(int[] nums, int[] cost) {
int n = nums.length;
Integer[] idx = new Integer[n];
for (int i = 0; i < n; i++) idx[i] = i;
Arrays.sort(idx, (a, b) -> nums[a] - nums[b]);
long total = 0;
for (int c : cost) total += c;
double half = total / 2.0;
long acc = 0;
int target = nums[idx[0]];
for (int k = 0; k < n; k++) {
acc += cost[idx[k]];
if (acc >= half) { target = nums[idx[k]]; break; }
}
long ans = 0;
for (int i = 0; i < n; i++) ans += (long) cost[i] * Math.abs(nums[i] - target);
return ans;
}
}long long minCost(vector<int>& nums, vector<int>& cost) {
int n = nums.size();
vector<pair<int, int>> pairs(n);
for (int i = 0; i < n; i++) pairs[i] = {nums[i], cost[i]};
sort(pairs.begin(), pairs.end());
long long total = 0;
for (int c : cost) total += c;
double half = total / 2.0;
long long acc = 0;
int target = pairs[0].first;
for (auto& p : pairs) {
acc += p.second;
if (acc >= half) { target = p.first; break; }
}
long long ans = 0;
for (int i = 0; i < n; i++) ans += (long long) cost[i] * abs(nums[i] - target);
return ans;
}Explanation
We need to pick one target value and pull every number to it. The total bill is Σ cost[i] · |nums[i] − target|. The brute-force idea is to try every candidate target between the smallest and largest number and keep the cheapest — that works, but the range of values can be huge, so we want something smarter.
Think of each number as having a weight equal to its cost. If you imagine the numbers laid out on a line, the value that minimizes the total weighted distance is the weighted median. Intuitively, if more weight sits to the right of your current target, you can always slide right and lower the bill; you stop exactly where the weight on each side balances.
To find that point, sort the (value, cost) pairs by value and walk through them while adding up the costs. The first value at which the running total reaches half of the total weight is the weighted median — our optimal target.
Example: nums = [1, 3, 5, 2], cost = [2, 3, 1, 14]. Sorted by value: (1,2), (2,14), (3,3), (5,1). Total weight is 20, so half is 10. Prefix sums are 2, then 2+14 = 16, which is the first time we hit or pass 10 — so the target is 2.
Finally we compute the bill at target 2: 2·1 + 14·0 + 3·1 + 1·3 = 8. That is the answer. Because the cost function is convex (V-shaped) in the target, this single balance point is guaranteed to be the global minimum.