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:
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 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] <= 106The key observation in #2448 Minimum Cost to Make Array Equal is that changing all elements to a target value incurs a weighted absolute difference cost. Since the cost function behaves like a convex function, the optimal value lies near a weighted central point of the array. A common strategy is to pair values with their costs, sort them, and use prefix sums to efficiently compute the total cost for converting all elements to a candidate value.
Instead of recomputing costs repeatedly, prefix sums allow constant-time cost evaluation for the left and right sides of a chosen element. Another practical idea is searching the optimal target using binary search over the value range, since the cost curve is convex and decreases before the minimum and increases afterward.
Sorting combined with prefix-sum cost calculations leads to an efficient solution that scales well for large inputs. The overall complexity is typically O(n log n) time with O(n) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting + Prefix Sum Cost Calculation | O(n log n) | O(n) |
| Binary Search on Target Value with Cost Evaluation | O(n log R) | O(1) |
Algorithms Made Easy
Use these hints if you're stuck. Try solving on your own first.
Changing the elements into one of the numbers already existing in the array nums is optimal.
Try finding the cost of changing the array into each element, and return the minimum value.
This approach involves treating the problem as a minimization problem where the minimum total cost is calculated by iterating over potential target values using binary search. At each step, the cost to make all elements equal to a proposed target is calculated, and the goal is to find the target that results in the minimal cost. By narrowing the range of potential target values using binary search, this approach efficiently finds the optimal target.
Time Complexity: O(n log(MAX_DIFF)), where MAX_DIFF is the range of possible numbers.
Space Complexity: O(1) since it only uses a fixed amount of extra space.
1using System;
2using System.Linq;
3
4public class MinCostEqualArray
5{
6 public static long CalculateCost(int[] nums, int[] cost, int target)
7 {
8 long totalCost = 0;
9 for (int i = 0; i < nums.Length; i++)
10 {
11 totalCost += Math.Abs(nums[i] - target) * (long)cost[i];
12 }
13 return totalCost;
14 }
public static long MinCost(int[] nums, int[] cost)
{
int minNum = nums.Min();
int maxNum = nums.Max();
long result = long.MaxValue;
while (minNum <= maxNum)
{
int midNum = minNum + (maxNum - minNum) / 2;
long costMid = CalculateCost(nums, cost, midNum);
long costMidPlusOne = CalculateCost(nums, cost, midNum + 1);
result = Math.Min(costMid, costMidPlusOne);
if (costMid < costMidPlusOne)
{
maxNum = midNum - 1;
}
else
{
minNum = midNum + 1;
}
}
return result;
}
public static void Main()
{
int[] nums = { 1, 3, 5, 2 };
int[] cost = { 2, 3, 1, 14 };
Console.WriteLine("Minimum cost: " + MinCost(nums, cost));
}
}This C# solution adopts LINQ methods for finding minimum and maximum values of the nums array to define binary search intervals. It continues similarly with a binary search to find the target that results in the minimum equalization cost.
The main idea is to use the concept of a weighted median to find the optimal target, a value to which all elements should be equalized to minimize cost. The weighted median is the best choice for minimizing the cost because it balances out the costs by taking into account where the bulk of weights lie. By considering each element's weight (cost), the weighted median is a statistically optimal choice that minimizes the total cost for the adjustment.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for auxiliary space used in sorting.
1def min_cost(nums, cost):
2 zipped_pairs = sorted(zip(
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, binary search can be applied to the possible target value range because the total cost function is convex. By comparing costs at nearby points, you can move toward the minimum efficiently.
Yes, this type of weighted optimization problem is common in FAANG-style interviews. It tests understanding of greedy reasoning, prefix sums, and recognizing convex cost behavior.
Prefix sums allow you to quickly calculate cumulative costs for elements on the left and right of a chosen target value. This avoids recomputing the total cost repeatedly and reduces the per-evaluation complexity to constant time after preprocessing.
The optimal approach usually involves sorting the numbers along with their costs and using prefix sums to compute weighted adjustment costs efficiently. Because the cost behaves like a convex function, the minimum often occurs around the weighted median of the values.
This Python solution involves sorting an array of pairs [num, cost], aiming to identify the weighted median. We accumulate the weights and find a point where the accumulated weight is equal to or exceeds half the total weight, signifying the median. That value is used as the target, minimizing the total cost of modification via a single pass.