Minimum Cost to Make Array Equal - Solution & Explanation
Problem Statement
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
Approach Overview
Problem 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 1: Approach 1: Binary Search on Result
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.
This C solution first finds the minimum and maximum numbers in the nums array to set the bounds for the binary search. It searches for the target value using binary search that minimizes the total cost to make all elements in nums equal to the target.
Complexity
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.
Approach 2: Approach 2: Weighted Median
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.
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.
Code
Python
Complexity
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for auxiliary space used in sorting.
Approach 3: Prefix Sum + Sorting + Enumeration
Let's denote the elements of the array nums as a_1, a_2, cdots, a_n and the elements of the array cost as b_1, b_2, cdots, b_n. We can assume that a_1 leq a_2 leq cdots leq a_n, i.e., the array nums is sorted in ascending order.
Suppose we change all elements in the array nums to x, then the total cost we need is:
$
\begin{aligned}
sum_{i=1}^{n} \left | a_i-x \right | b_i &= sum_{i=1}^{k} (x-a_i)b_i + sum_{i=k+1}^{n} (a_i-x)b_i \
&= xsum_{i=1}^{k} b_i - sum_{i=1}^{k} a_ib_i + sum_{i=k+1}^{n}a_ib_i - xsum_{i=k+1}^{n}b_i
\end{aligned}
where k is the number of elements in a_1, a_2, cdots, a_n that are less than or equal to x.
We can use the prefix sum method to calculate sum_{i=1}^{k} b_i and sum_{i=1}^{k} a_ib_i, as well as sum_{i=k+1}^{n}a_ib_i and sum_{i=k+1}^{n}b_i.
Then we enumerate x, calculate the above four prefix sums, get the total cost mentioned above, and take the minimum value.
The time complexity is O(ntimes log n), where n$ is the length of the array nums. The main time complexity comes from sorting.
Approach 4: Sorting + Median
We can also consider b_i as the occurrence times of a_i, then the index of the median is \frac{sum_{i=1}^{n} b_i}{2}. Changing all numbers to the median is definitely optimal.
The time complexity is O(ntimes log n), where n is the length of the array nums. The main time complexity comes from sorting.
Similar problems:
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Binary Search on Result | Time Complexity: O(n log(MAX_DIFF)), where MAX_DIFF is the range of possible numbers. |
| Approach 2: Weighted Median | Time Complexity: O(n log n) due to sorting. |
| Prefix Sum + Sorting + Enumeration | — |
| Sorting + Median | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Minimum Cost to Make Array Equal | Simplest Solution | MICROSOFT | Leetcode-2448 | Explanation • codestorywithMIK • 15,761 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Cost to Make Array Equal easy or hard?
Minimum Cost to Make Array Equal Python/Java solution
How to solve Minimum Cost to Make Array Equal in O(n)?
What is the best approach for Minimum Cost to Make Array Equal?
Is Minimum Cost to Make Array Equal asked at Google/Amazon/Meta?
What data structure is used in Minimum Cost to Make Array Equal?
What is the time complexity of Minimum Cost to Make Array Equal?
Ready to solve this problem?
Practice Minimum Cost to Make Array Equal with our built-in code editor and test cases.
Practice on FleetCode