2448

2448. Minimum Cost to Make Array Equal (Hard)

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 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.length
• 1 <= n <= 105
• 1 <= nums[i], cost[i] <= 106
• Test cases are generated in a way that the output doesn't exceed 2⁵³-1

Companies: Google, Amazon, Cisco

Related Topics:
Array, Binary Search, Greedy, Sorting, Prefix Sum

Similar Questions:

• Minimum Moves to Equal Array Elements II (Medium)
• Maximum Product of the Length of Two Palindromic Substrings (Hard)
• Minimum Amount of Time to Fill Cups (Easy)
• Minimum Operations to Make All Array Elements Equal (Medium)

Solution 1. Left-to-right State Transition

We first sort the arrays together in accending order of the numbers.

For example, A = [1,3,5,2], C = [2,3,1,14], then after sorting, they become A = [1,2,3,5], C = [2,14,3,1].

We scan the numbers from left to right.

Let rightSum be the sum of costs of numbers greater than or equal to the current number, leftSum be the cost of numbers smaller than the current number, totalCost be the total cost needed to change all numbers to be the same as the current number.

When we move from A[i-1] to A[i], let d = A[i] - A[i-1], the totalCost need to - d * rightSum and + d * leftSum.

For example, A = [1,2,3,5], C = [2,14,3,1]. When we move from A[0] = 1 to A[1] = 2, d = 1, the totalCost at A[0] was 0 * 2 + 1 * 14 + 2 * 3 + 4 * 1, and now we need to change totalCost by - d * rightSum = -1 * (14 + 3 + 1) and + d * leftSum = +1 * (2), so the totalCost becomes 1 * 2 + 0 * 14 + 1 * 3 + 3 * 1.

After calculating totalCost for A[i], we update rightSum by -C[i] and leftSum by +C[i].

// OJ: https://leetcode.com/problems/minimum-cost-to-make-array-equal
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    long long minCost(vector<int>& A, vector<int>& C) {
        long long rightSum = accumulate(begin(C), end(C), 0LL), leftSum = 0, ans = LLONG_MAX, N = A.size(), prev = 0, totalCost = 0;
        vector<int> id(N);
        iota(begin(id), end(id), 0);
        sort(begin(id), end(id), [&](int a, int b) { return A[a] < A[b]; });
        for (int i = 0; i < N; ++i) totalCost += (long long)A[i] * C[i];
        for (int i = 0; i < N; ++i) {
            long long num = A[id[i]], cost = C[id[i]], d = num - prev;
            totalCost = totalCost + d * (leftSum - rightSum);
            ans = min(ans, totalCost);
            rightSum -= cost;
            leftSum += cost;
            prev = num;
        }
        return ans;
    }
};

Solution 2. Binary Search

Intuition

This approach is based on one theorem: a linear combination (with non-negative coefficients) of convex functions is convex.

You might find more information of convex function here

Here, we define fi(x)f_i(x)fi​(x) as the cost function if nums only contains one element nums[i].

If nums only contains nums[i], the cost function fi(x)f_i(x)fi​(x) is convex, as shown in the picture below.

If nums consists of multiple elements, the cost F(x)F(x)F(x) is the combination of every fi(x)f_i(x)fi​(x), that is F(x)=f1(x)+f2(x)+...F(x) = f_1(x) + f_2(x) + ... F(x)=f1​(x)+f2​(x)+... where each fi(x)f_i(x)fi​(x) is convex.

Therefore, the total cost function F(x)F(x)F(x) is convex and has the minimum mi in the range [min(nums), max(nums)].

Therefore, we can use binary search to locate the minimum of this convex function. Start with setting the boundaries of the search space as left = min(nums) and right = max(nums), we cut the search space into two halves by mid = (left + right) / 2. Then we shall determine which part contains the minimum cost. This can be done by comparing the cost of two adjacent bases:

• If F(x)<F(x+1)F(x) < F(x + 1)F(x)<F(x+1), it means the base that brings the minimum cost is on F(x)F(x)F(x)'s left, thus we should cut the right half.
• If F(x)>=F(x+1)F(x) >= F(x + 1)F(x)>=F(x+1), it means the base that brings the minimum cost is on F(x)F(x)F(x)'s right, thus we should cut the left half.

We continue the binary search until we reach the base that brings the minimum cost.

Algorithm

1. Initialize the searching space by setting its boundaries left = min(nums) and right = max(nums).

2）While left < right:

• Get the middle value mid using integer division mid = (left + right) / 2.
• Calculate the cost of two adjacent bases, F(mid) and F(mid + 1).
• If F(mid) > F(mid + 1), cut the left half by setting left = mid + 1. Otherwise, cut the right half by setting right = mid. Then repeat step 2.

3. Return left once the search ends.

// OJ: https://leetcode.com/problems/minimum-cost-to-make-array-equal
// Author: github.com/lzl124631x
// Time: O(NlogK)
// Space: O(1)
class Solution {
public:
    long long minCost(vector<int>& A, vector<int>& C) {
        long long ans = LLONG_MAX, L = *min_element(begin(A), end(A)), R = *max_element(begin(A), end(A)), N = A.size();
        auto cost = [&](int to) {
            long long ans = 0;
            for (int i = 0; i < N; ++i) ans += (long long)abs(A[i] - to) * C[i];
            return ans;
        };
        while (L <= R) {
            long long M = (L + R) / 2, a = cost(M), b = cost(M + 1);
            ans = min(a, b);
            if (a > b) L = M + 1;
            else R = M - 1;
        }
        return ans;
    }
};