.png)
Minimum Cost to Make Array Equal
Problem Statement
You are given two integer arrays:
- nums → values
- cost → cost to increment or decrement the corresponding value by 1
In one operation, you can increase or decrease nums[i] by 1 at a cost of cost[i].
Your task is to make all elements of nums equal with minimum total cost.
Example
Input
nums = [1,3,5,2]
cost = [2,3,1,14]
Output
8
Explanation
Make all elements equal to 2
| Element | Change | Cost |
|---|---|---|
| 1 → 2 | +1 | 2 |
| 3 → 2 | -1 | 3 |
| 5 → 2 | -3 | 3 |
| 2 → 2 | 0 | 0 |
Total cost = 8
Why This Problem Is Important
- Asked in Google, Amazon, Meta
- Tests:
- Weighted median concept
- Convex cost functions
- Optimization intuition
- Foundation for:
- Cost minimization
- Convex optimization
- Binary search on value
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force (Try all targets) | O(n·range) | O(1) |
| Approach 2 | Binary Search on Answer | O(n log range) | O(1) |
| Approach 3 | Weighted Median (Optimal) | O(n log n) | O(1) |
Approach 1: Brute Force (Try All Targets)
Idea
- Try every possible target value between min and max
- Compute total cost
- Take minimum
Time & Space
- Time: O(n × range)
- Space: O(1)
C
#include
#include
int absVal(int x){ return x < 0 ? -x : x; }
int main() {
int nums[] = {1,3,5,2};
int cost[] = {2,3,1,14};
int n = 4;
int minVal = nums[0], maxVal = nums[0];
for(int i=1;i maxVal) maxVal = nums[i];
}
long long ans = LLONG_MAX;
for(int t=minVal; t<=maxVal; t++){
long long total = 0;
for(int i=0;iC++
#include
using namespace std;
int main() {
vector nums = {1,3,5,2};
vector cost = {2,3,1,14};
int lo = *min_element(nums.begin(), nums.end());
int hi = *max_element(nums.begin(), nums.end());
long long ans = LLONG_MAX;
for(int t = lo; t <= hi; t++){
long long curr = 0;
for(int i=0;iJava
class MinCostBrute {
public static void main(String[] args) {
int[] nums = {1,3,5,2};
int[] cost = {2,3,1,14};
int min = nums[0], max = nums[0];
for(int x : nums){
min = Math.min(min, x);
max = Math.max(max, x);
}
long ans = Long.MAX_VALUE;
for(int t = min; t <= max; t++){
long sum = 0;
for(int i=0;iPython
nums = [1,3,5,2]
cost = [2,3,1,14]
ans = float('inf')
for t in range(min(nums), max(nums)+1):
total = 0
for i in range(len(nums)):
total += abs(nums[i] - t) * cost[i]
ans = min(ans, total)
print(ans)
JavaScript
let nums = [1,3,5,2];
let cost = [2,3,1,14];
let lo = Math.min(...nums);
let hi = Math.max(...nums);
let ans = Infinity;
for(let t = lo; t <= hi; t++){
let sum = 0;
for(let i=0;iC#
using System;
class Program {
static void Main() {
int[] nums = {1,3,5,2};
int[] cost = {2,3,1,14};
int min = nums[0], max = nums[0];
foreach(int x in nums){
min = Math.Min(min, x);
max = Math.Max(max, x);
}
long ans = long.MaxValue;
for(int t=min; t<=max; t++){
long sum = 0;
for(int i=0;iOutput
8
Approach 2: Binary Search on Target Value
Idea
- Cost function is convex
- Use binary search on answer
- Compare f(mid) and f(mid+1)
Time & Space
- Time: O(n log range)
- Space: O(1)
C
#include
long long calc(int t, int nums[], int cost[], int n){
long long sum = 0;
for(int i=0;i hi) hi = nums[i];
}
while(lo < hi){
int mid = (lo + hi) / 2;
if(calc(mid, nums, cost, n) <= calc(mid+1, nums, cost, n))
hi = mid;
else
lo = mid + 1;
}
printf("%lld", calc(lo, nums, cost, n));
}
C++
#include
using namespace std;
long long calc(int t, vector& nums, vector& cost){
long long s = 0;
for(int i=0;i nums = {1,3,5,2};
vector cost = {2,3,1,14};
int lo = *min_element(nums.begin(), nums.end());
int hi = *max_element(nums.begin(), nums.end());
while(lo < hi){
int mid = (lo + hi) / 2;
if(calc(mid, nums, cost) <= calc(mid+1, nums, cost))
hi = mid;
else
lo = mid + 1;
}
cout << calc(lo, nums, cost);
}
Java
class MinCostBinary {
static long calc(int t, int[] nums, int[] cost){
long sum = 0;
for(int i=0;iPython
def calc(t):
return sum(abs(nums[i]-t) * cost[i] for i in range(len(nums)))
nums = [1,3,5,2]
cost = [2,3,1,14]
l, r = min(nums), max(nums)
while l < r:
mid = (l + r) // 2
if calc(mid) <= calc(mid + 1):
r = mid
else:
l = mid + 1
print(calc(l))
JavaScript
function calc(t){
let s = 0;
for(let i=0;iC#
using System;
class Program {
static long Calc(int t, int[] nums, int[] cost){
long sum = 0;
for(int i=0;iOutput
8
Approach 3: Weighted Median (Optimal)
Key Insight
To minimize:
Σ |nums[i] - x| × cost[i]
x must be the weighted median
Steps
- Pair (value, cost)
- Sort by value
- Find weighted median
- Compute cost
Time & Space
- Time: O(n log n)
- Space: O(1)
Python
nums = [1,3,5,2]
cost = [2,3,1,14]
pairs = sorted(zip(nums, cost))
total = sum(cost)
curr = 0
target = 0
for v, c in pairs:
curr += c
if curr >= (total + 1)//2:
target = v
break
ans = sum(abs(nums[i]-target)*cost[i] for i in range(len(nums)))
print(ans)
C++
#include
using namespace std;
int main(){
vector nums = {1,3,5,2};
vector cost = {2,3,1,14};
vector> v;
for(int i=0;i= (total+1)/2){
target = p.first;
break;
}
}
long long ans = 0;
for(int i=0;iJava
import java.util.*;
class MinCostArray {
public static void main(String[] args){
int[] nums = {1,3,5,2};
int[] cost = {2,3,1,14};
int n = nums.length;
int[][] a = new int[n][2];
for(int i=0;i x[0] - y[0]);
long total = 0;
for(int[] x : a) total += x[1];
long curr = 0;
int target = 0;
for(int[] x : a){
curr += x[1];
if(curr >= (total+1)/2){
target = x[0];
break;
}
}
long ans = 0;
for(int i=0;iJavaScript
let nums = [1,3,5,2];
let cost = [2,3,1,14];
let pairs = nums.map((v,i)=>[v,cost[i]]);
pairs.sort((a,b)=>a[0]-b[0]);
let total = cost.reduce((a,b)=>a+b,0);
let curr = 0, target = 0;
for(let [v,c] of pairs){
curr += c;
if(curr >= Math.floor((total+1)/2)){
target = v;
break;
}
}
let ans = 0;
for(let i=0;iC#
using System;
using System.Linq;
class Program {
static void Main(){
int[] nums = {1,3,5,2};
int[] cost = {2,3,1,14};
var pairs = nums.Select((v,i)=>new {v, c=cost[i]})
.OrderBy(x=>x.v)
.ToArray();
long total = pairs.Sum(x=>x.c);
long curr = 0;
int target = 0;
foreach(var p in pairs){
curr += p.c;
if(curr >= (total+1)/2){
target = p.v;
break;
}
}
long ans = 0;
for(int i=0;iOutput
8
Final Summary
- Brute Force: Learning only
- Binary Search: Convex optimization
- Weighted Median: BEST & EXPECTED
Interview Rule
If cost is weighted → median becomes weighted median
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.png)
