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] <= 106This 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.
C++
Java
Python
C#
JavaScript
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.
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.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for auxiliary space used in sorting.
| 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. |
Minimum Operations to Make Array Equal | Leetcode - 1551 • Algorithms Made Easy • 24,165 views views
Watch 9 more video solutions →Practice Minimum Cost to Make Array Equal with our built-in code editor and test cases.
Practice on FleetCode