Minimum Cost to Make Array Equal
HardPrompt
You are given two 0-indexed arrays nums and cost consisting each of n positive integers.
You can do the following operation any number of times:
- Increase or decrease any element of the array
numsby1.
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 become equal.
Example 1:
Input: nums = [1,3,5,2], cost = [2,3,1,14]
Output: 8
Explanation: We can make all the elements equal to 2 in the following way:
- Increase the 0th element one time. The cost is 2.
- Decrease the 1st element one time. The cost is 3.
- Decrease the 2nd element three times. The cost is 1 + 1 + 1 = 3.
The total cost is 2 + 3 + 3 = 8.
It can be shown that we cannot make the array equal with a smaller cost.Example 2:
Input: nums = [2,2,2,2,2], cost = [4,2,8,1,3]
Output: 0
Explanation: All the elements are already equal, so no operations are needed.
Constraints:
n == nums.length == cost.length1 <= n <= 1051 <= nums[i], cost[i] <= 106- Test cases are generated in a way that the output doesn't exceed 253-1
Approaches
3 approaches with complexity analysis and trade-offs.
The core idea is to find the final equal value that all elements in nums will be converted to. A crucial observation is that this optimal target value must lie within the range of the minimum and maximum values present in the nums array. Any target value outside this range would result in a higher cost. Therefore, we can simply iterate through every possible integer target value from min(nums) to max(nums), calculate the total cost for each target, and find the minimum one.
Algorithm
- First, determine the search space by finding the minimum (
minVal) and maximum (maxVal) elements in thenumsarray. - Initialize a variable
minCostto a very large value to store the minimum cost found so far. - Iterate through each integer
targetfromminValtomaxVal. - For each
target, calculate thecurrentCostrequired to make all elements innumsequal totarget. This is done by summing upabs(nums[i] - target) * cost[i]for alli. - Compare
currentCostwithminCostand updateminCostifcurrentCostis smaller. - After checking all possible targets,
minCostwill hold the minimum possible cost.
Walkthrough
This method involves a straightforward check of all potential candidates for the final value.
class Solution { public long minCost(int[] nums, int[] cost) { long minCost = Long.MAX_VALUE; int minVal = Integer.MAX_VALUE; int maxVal = Integer.MIN_VALUE; for (int num : nums) { minVal = Math.min(minVal, num); maxVal = Math.max(maxVal, num); } for (int target = minVal; target <= maxVal; target++) { long currentCost = 0; for (int i = 0; i < nums.length; i++) { currentCost += (long) Math.abs(nums[i] - target) * cost[i]; } minCost = Math.min(minCost, currentCost); } return minCost; }}Complexity
Time
O(N * M), where N is the length of the arrays and M is the difference between the maximum and minimum values in `nums`. This is because we have a nested loop structure: the outer loop runs M times and the inner loop runs N times.
Space
O(1), as we only use a few variables to store state, regardless of the input size.
Trade-offs
Pros
Simple to conceptualize and implement.
Cons
Extremely inefficient for large ranges of
numsvalues, leading to a Time Limit Exceeded error on most platforms.
The total cost, as a function of the target value x, is f(x) = sum(|nums[i] - x| * cost[i]). This function is a sum of V-shaped functions, which results in a convex (U-shaped) function. A key property of a convex function is that it has a single minimum. This allows us to use a binary search-like approach to find this minimum efficiently. By comparing the costs at two nearby points, we can determine which direction to search in, effectively halving the search space in each step.
Algorithm
- Define the search range
[low, high]for the target value. A safe range is from 1 to 1,000,000, as given by the problem constraints. - Create a helper function,
calculateCost(target), which takes a target value and computes the total cost to make allnumselements equal to it in O(N) time. - Use a
whileloop to perform the binary search as long aslow <= high. - In each iteration, calculate a midpoint
mid. - Compare the cost at
midwith the cost atmid + 1. Let them becost1andcost2. - If
cost1 < cost2, it implies the minimum is located at or to the left ofmid. Thus, we can discard the right half by settinghigh = mid - 1. - If
cost1 >= cost2, the minimum is at or to the right ofmid + 1. We discard the left half by settinglow = mid + 1. - Keep track of the minimum cost found during this process. The final answer will be the minimum of all
cost1andcost2values computed.
Walkthrough
Instead of a linear scan, we can intelligently narrow down the search space for the optimal target value.
class Solution { public long minCost(int[] nums, int[] cost) { int low = 1; int high = 1000000; // From constraints long ans = Long.MAX_VALUE; while (low <= high) { int mid = low + (high - low) / 2; long cost1 = calculateCost(nums, cost, mid); long cost2 = calculateCost(nums, cost, mid + 1); ans = Math.min(cost1, cost2); if (cost1 < cost2) { high = mid - 1; } else { low = mid + 1; } } return ans; } private long calculateCost(int[] nums, int[] cost, int target) { long totalCost = 0L; for (int i = 0; i < nums.length; i++) { totalCost += (long) Math.abs(nums[i] - target) * cost[i]; } return totalCost; }}Complexity
Time
O(N * log M), where N is the array length and M is the search range size (e.g., 10^6). The binary search performs `log M` iterations, and each iteration calls `calculateCost`, which takes O(N) time.
Space
O(1), as the search is done in-place without requiring extra space proportional to the input size.
Trade-offs
Pros
Much more efficient than brute force.
Guaranteed to find the minimum for a convex function.
Cons
The cost function is calculated repeatedly, which might be less efficient than a single-pass algorithm after sorting.
This problem can be elegantly solved by identifying it as a search for the weighted median. The expression sum(cost[i] * |nums[i] - x|) is minimized when x is the weighted median of the numbers in nums, where cost[i] are the weights. The weighted median is the value that partitions the sorted weights into two equal halves. Once we find this median value, we can calculate the minimum cost.
Algorithm
- Create an array of pairs, where each pair contains
(nums[i], cost[i]). - Calculate the sum of all costs, let's call it
totalWeight. - Sort the array of pairs based on the
numsvalues in ascending order. - Iterate through the sorted pairs and maintain a
cumulativeWeight. In each step, add the cost of the current pair tocumulativeWeight. - The weighted median is the number from the first pair for which
cumulativeWeightbecomes greater than or equal to half oftotalWeight. Let this number bemedianNum. - The minimum cost is then the total cost to make all elements equal to
medianNum. Calculate this by summingabs(nums[i] - medianNum) * cost[i]for all originali.
Walkthrough
The most efficient approach involves sorting the numbers and finding the point where the cumulative cost (weight) crosses the halfway point of the total cost.
import java.util.Arrays;import java.util.Comparator; class Solution { public long minCost(int[] nums, int[] cost) { int n = nums.length; int[][] pairs = new int[n][2]; long totalWeight = 0; for (int i = 0; i < n; i++) { pairs[i][0] = nums[i]; pairs[i][1] = cost[i]; totalWeight += cost[i]; } Arrays.sort(pairs, Comparator.comparingInt(a -> a[0])); long medianNum = -1; long cumulativeWeight = 0; for (int i = 0; i < n; i++) { cumulativeWeight += pairs[i][1]; if (cumulativeWeight * 2 >= totalWeight) { medianNum = pairs[i][0]; break; } } long minTotalCost = 0; for (int i = 0; i < n; i++) { minTotalCost += (long) Math.abs(nums[i] - medianNum) * cost[i]; } return minTotalCost; }}Complexity
Time
O(N log N), dominated by the sorting step. The subsequent passes to find the median and calculate the final cost take O(N) time.
Space
O(N), required to store the pairs of `(num, cost)` for sorting.
Trade-offs
Pros
This is the most efficient and standard approach for this type of problem.
It directly identifies the optimal target value with mathematical reasoning.
Cons
Requires extra space to store pairs for sorting.
Solutions
Solution
class Solution {public long minCost(int[] nums, int[] cost) { int n = nums.length; int[][] arr = new int[n][2]; for (int i = 0; i < n; ++i) { arr[i] = new int[]{nums[i], cost[i]}; } Arrays.sort(arr, (a, b)->a[0] - b[0]); long[] f = new long[n + 1]; long[] g = new long[n + 1]; for (int i = 1; i <= n; ++i) { long a = arr[i - 1][0], b = arr[i - 1][1]; f[i] = f[i - 1] + a * b; g[i] = g[i - 1] + b; } long ans = Long.MAX_VALUE; for (int i = 1; i <= n; ++i) { long a = arr[i - 1][0]; long l = a * g[i - 1] - f[i - 1]; long r = f[n] - f[i] - a * (g[n] - g[i]); ans = Math.min(ans, l + r); } return ans; }}using ll = long long ; class Solution { public: long long minCost ( vector < int >& nums , vector < int >& cost ) { int n = nums . size (); vector < pair < int , int >> arr ( n ); for ( int i = 0 ; i < n ; ++ i ) arr [ i ] = { nums [ i ], cost [ i ]}; sort ( arr . begin (), arr . end ()); vector < ll > f ( n + 1 ), g ( n + 1 ); for ( int i = 1 ; i <= n ; ++ i ) { auto [ a , b ] = arr [ i - 1 ]; f [ i ] = f [ i - 1 ] + 1ll * a * b ; g [ i ] = g [ i - 1 ] + b ; } ll ans = 1e18 ; for ( int i = 1 ; i <= n ; ++ i ) { auto [ a , _ ] = arr [ i - 1 ]; ll l = 1ll * a * g [ i - 1 ] - f [ i - 1 ]; ll r = f [ n ] - f [ i ] - 1ll * a * ( g [ n ] - g [ i ]); ans = min ( ans , l + r ); } return ans ; } };class Solution: def minCost(self, nums: List[int], cost: List[int]) -> int: arr = sorted(zip(nums, cost)) n = len(arr) f = [0] * (n + 1) g = [0] * (n + 1) for i in range(1, n + 1): a, b = arr[i - 1] f[i] = f[i - 1] + a * b g[i] = g[i - 1] + b ans = inf for i in range(1, n + 1): a = arr[i - 1][0] l = a * g[i - 1] - f[i - 1] r = f[n] - f[i] - a * (g[n] - g[i]) ans = min(ans, l + r) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.