Minimum Cost to Make Array Equal — Problem & Solution
Minimum Cost to Make Array Equal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Minimum Cost to Make Array Equal is a hard coding problem on arrays, sorting and greedy, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Arrays, Sorting, Greedy, Binary Search
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two arrays of length n: nums and cost. One operation increases or decreases a single element nums[i] by 1 and costs cost[i].
Return the minimum total cost to make every element of nums equal.
CodeKairo bounds: the original allows values and costs up to 10^6 with n up to 10^5, which needs a 64-bit answer. Here n <= 10^4, nums[i] <= 10^4 and cost[i] <= 10, so the answer fits in a 32-bit integer.
Example 1
Input: nums = [1,3,5,2], cost = [2,3,1,14]
Output: 8
Explanation: Make every element 2: 1·2 + 1·3 + 3·1 + 0·14 = 8.
Example 2
Input: nums = [2,2,2,2,2], cost = [4,2,8,1,3]
Output: 0
Example 3
Input: nums = [10,1], cost = [1,5]
Output: 9
Explanation: Moving the cheap element all the way costs 9; any other meeting point costs more.
Constraints
n == nums.length == cost.length1 <= n <= 10^41 <= nums[i] <= 10^41 <= cost[i] <= 10
Hints for Minimum Cost to Make Array Equal
Hint 1
Write the cost of making everything equal to
xas a functionf(x) = Σ |nums[i] - x| · cost[i].Hint 2
Each term is a V shape, so
fis convex: it decreases, then (maybe after a flat stretch) increases.Hint 3
Binary-search
xbetweenmin(nums)andmax(nums)by comparingf(mid)withf(mid + 1).
How to solve Minimum Cost to Make Array Equal
The total cost as a function of the common target x is a sum of weighted absolute values, which is convex. The minimum of a convex function over integers can be binary-searched by looking at the sign of its slope f(mid + 1) - f(mid).
Approach
- Let
lo = min(nums),hi = max(nums)— moving outside that range only adds cost. - While
lo < hi: takemid = lo + (hi - lo) / 2; iff(mid) <= f(mid + 1)the minimum is atmidor to its left (hi = mid), otherwise it is to the right (lo = mid + 1). - Return
f(lo), computingfwith 64-bit accumulation.
Why it works
Each |nums[i] - x| · cost[i] is convex in x, and sums of convex functions are convex, so the slope f(x + 1) - f(x) is non-decreasing. Where it is still negative the minimum lies further right; once it is zero or positive, nothing to the right can be lower than f(mid). That is exactly the invariant the search keeps. (Equivalently, the optimum is the cost-weighted median of nums.)
Complexity
- Time —
O(n log V) with V the value range - Space —
O(1)
Pitfalls
- Evaluate
fin 64-bit — at a badxthe sum can exceed what the answer needs. - Compare
f(mid)withf(mid + 1), not withf(mid - 1), to keepmid + 1inside the range. - A target outside
[min, max]is never better, so the search range is safe.
Reference solution
Python
from typing import List
def minCost(nums: List[int], cost: List[int]) -> int:
def f(x):
return sum(abs(a - x) * c for a, c in zip(nums, cost))
lo, hi = min(nums), max(nums)
while lo < hi:
mid = (lo + hi) // 2
if f(mid) <= f(mid + 1):
hi = mid
else:
lo = mid + 1
return f(lo)Java
public static int minCost(int[] nums, int[] cost) {
int lo = Integer.MAX_VALUE, hi = Integer.MIN_VALUE;
for (int v : nums) { lo = Math.min(lo, v); hi = Math.max(hi, v); }
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (costAt(nums, cost, mid) <= costAt(nums, cost, mid + 1)) hi = mid; else lo = mid + 1;
}
return (int) costAt(nums, cost, lo);
}
static long costAt(int[] nums, int[] cost, int x) {
long s = 0;
for (int i = 0; i < nums.length; i++) s += (long) Math.abs(nums[i] - x) * cost[i];
return s;
}C++
long long costAt(const vector<int>& nums, const vector<int>& cost, int x) {
long long s = 0;
for (size_t i = 0; i < nums.size(); i++) s += (long long)abs(nums[i] - x) * cost[i];
return s;
}
int minCost(vector<int>& nums, vector<int>& cost) {
int lo = *min_element(nums.begin(), nums.end());
int hi = *max_element(nums.begin(), nums.end());
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (costAt(nums, cost, mid) <= costAt(nums, cost, mid + 1)) hi = mid; else lo = mid + 1;
}
return (int)costAt(nums, cost, lo);
}JavaScript
var minCost = function(nums, cost) {
var f = function(x) {
var s = 0;
for (var i = 0; i < nums.length; i++) s += Math.abs(nums[i] - x) * cost[i];
return s;
};
var lo = Infinity, hi = -Infinity;
for (var j = 0; j < nums.length; j++) {
if (nums[j] < lo) lo = nums[j];
if (nums[j] > hi) hi = nums[j];
}
while (lo < hi) {
var mid = lo + ((hi - lo) >> 1);
if (f(mid) <= f(mid + 1)) hi = mid; else lo = mid + 1;
}
return f(lo);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms