Watch 10 video solutions for Minimum Cost to Make Array Equal, a hard level problem involving Array, Binary Search, Greedy. This walkthrough by codestorywithMIK has 14,319 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 106Problem Overview: You are given two arrays nums and cost. Changing nums[i] to any value costs |nums[i] - x| * cost[i]. The task is to choose a target value x so that converting every element to x produces the minimum total cost.
Approach 1: Binary Search on Result (Time: O(n log M), Space: O(1))
The total cost function is convex with respect to the chosen target value x. As x moves across the number line, the cost decreases until a minimum point and then increases. Convex functions allow binary search on the answer. Pick a mid value and compute the total cost by iterating through the array and summing |nums[i] - mid| * cost[i]. Compare it with the cost at mid + 1. If the cost decreases, move right; otherwise move left. Each evaluation scans the array once, giving O(n) work per step and O(log M) search steps where M is the value range. This technique is common when optimizing a monotonic or convex function using binary search.
Approach 2: Weighted Median (Time: O(n log n), Space: O(1) or O(n) depending on implementation)
The expression |nums[i] - x| * cost[i] represents a weighted absolute distance. The value minimizing the sum of weighted absolute differences is the weighted median. Pair each value with its weight, sort the pairs by value using sorting, and accumulate weights until the prefix weight reaches at least half of the total weight. The corresponding value becomes the optimal target. After identifying this weighted median, compute the final cost with a single pass through the array. The key insight: absolute deviation is minimized at the median, and weights simply stretch the contribution of each element.
This method avoids searching the numeric range entirely. Instead, it relies on ordering and cumulative weights, conceptually similar to using prefix sums to track running totals. Once the weighted median is known, the optimal cost follows directly.
Recommended for interviews: The weighted median approach is usually the expected optimal insight. It shows you recognize that minimizing weighted absolute distance leads to a median-based solution. Binary search on the result is still a strong alternative because it demonstrates understanding of convex optimization and works even when the optimal structure is not obvious.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search on Result | O(n log M) | O(1) | General optimization problems where the cost function is convex over a numeric range |
| Weighted Median | O(n log n) | O(1) to O(n) | Best when minimizing weighted absolute differences; relies on sorting and cumulative weights |