#2448

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Minimum Cost to Make Array Equal

Find the minimum cost to make all elements of an array equal by using binary search over valid answers.

array binary search greedy sorting prefix sum

Problem Statement

You are given two arrays, nums and cost, both of length n, where nums[i] is the ith element and cost[i] represents the cost of changing nums[i] to any value. Your goal is to make all elements in nums equal with the least cost. The cost of changing any element nums[i] to a new value is cost[i] multiplied by the number of changes required.

To solve the problem, you can perform any number of operations where you change the ith element of the array. The cost of changing the element depends on the cost array. Your task is to compute the minimum possible cost to make all elements of nums the same value.

Examples

Example 1

Input: nums = [1,3,5,2], cost = [2,3,1,14]

Output: 8

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

All the elements are already equal, so no operations are needed.

Constraints

n == nums.length == cost.length
1 <= n <= 105
1 <= nums[i], cost[i] <= 106
Test cases are generated in a way that the output doesn't exceed 253-1

Solution Approach

Binary Search on Answer Space

The optimal target value for the array is one of the values already present in nums. Binary search is used to determine the minimum cost by testing each candidate value as the target and calculating the total cost of converting all elements to this value.

Prefix Sum Optimization

Using a prefix sum to compute cumulative costs for transforming the elements helps speed up the process of calculating the total transformation cost. This makes the solution more efficient by reducing redundant recalculations.

Greedy Cost Calculation

For each target value, calculate the total cost of transforming all elements of nums to that target. Since the transformation cost is directly tied to the differences in values, we use a greedy approach to ensure the minimal cost for each candidate.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity primarily depends on the binary search over the answer space, combined with the greedy calculations for each potential target value. For each candidate target, we must compute the total cost, leading to a complexity of O(n log m), where n is the number of elements and m is the number of distinct values in nums.

What Interviewers Usually Probe

The candidate should identify that binary search is essential for minimizing the cost by narrowing the search space to only valid targets.
The solution should use efficient data structures like prefix sums to optimize the calculation of transformation costs.
A deep understanding of greedy algorithms is expected to efficiently calculate the transformation cost for each target value.

Common Pitfalls or Variants

Common pitfalls

Failing to recognize that the target value should be one of the existing elements in nums, leading to incorrect or suboptimal solutions.
Not optimizing the calculation of transformation costs using prefix sums, resulting in slower solutions.
Overlooking the need to consider all potential target values and missing the most efficient transformation cost.

Follow-up variants

What if the nums array contains negative numbers or zeros? The approach would need to be adjusted to handle non-positive integers.
What if the cost array allows for fractional costs? This could change the nature of the binary search and how costs are calculated.
How would this problem scale if we had to handle multiple arrays or matrices, increasing the size of the input?

FAQ

How do I minimize the cost to make all elements equal in the Minimum Cost to Make Array Equal problem?

By using binary search over the valid answer space, and leveraging prefix sums and a greedy approach to calculate the total transformation cost for each target value.

Why should I use binary search for this problem?

Binary search is used to efficiently find the optimal target value by narrowing down the possible candidates, reducing the overall computation time.

What makes the greedy approach necessary in this problem?

The greedy approach ensures that for each target value, the transformation costs are minimized by directly calculating the cost for each candidate value.

What are the most common mistakes in solving the Minimum Cost to Make Array Equal problem?

Common mistakes include overlooking that the target value should be one of the existing values in nums and not optimizing the cost calculation using prefix sums.

What is the role of the cost array in this problem?

The cost array determines how much it will cost to change each element of nums to the target value, and is crucial for computing the minimum transformation cost.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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 ans

Solution 2: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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 ans

Continue Practicing

#2389 longest subsequence with limited sum #2271 maximum white tiles covered by a carpet #2234 maximum total beauty of the gardens