Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2448.html

2448. Minimum Cost to Make Array Equal

  • Difficulty: Hard.
  • Related Topics: Array, Binary Search, Sorting, Prefix Sum.
  • Similar Questions: Minimum Moves to Equal Array Elements II, Maximum Product of the Length of Two Palindromic Substrings, Minimum Amount of Time to Fill Cups.

Problem

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

Solution (Java, C++, Python)

  • class Solution {
        public long minCost(int[] nums, int[] cost) {
            int n = nums.length;
            int[][] arr = new int[n][2];
            for (int i = 0; i < n; ++i) {
                arr[i] = new int[]{nums[i], cost[i]};
            }
            Arrays.sort(arr, (a, b) -> a[0] - b[0]);
            long[] f = new long[n + 1];
            long[] g = new long[n + 1];
            for (int i = 1; i <= n; ++i) {
                long a = arr[i - 1][0], b = arr[i - 1][1];
                f[i] = f[i - 1] + a * b;
                g[i] = g[i - 1] + b;
            }
            long ans = Long.MAX_VALUE;
            for (int i = 1; i <= n; ++i) {
                long a = arr[i - 1][0];
                long l = a * g[i - 1] - f[i - 1];
                long r = f[n] - f[i] - a * (g[n] - g[i]);
                ans = Math.min(ans, l + r);
            }
            return ans;
        }
    }
    
  • using ll = long long;
    
    class Solution {
    public:
        long long minCost(vector<int>& nums, vector<int>& cost) {
            int n = nums.size();
            vector<pair<int, int>> arr(n);
            for (int i = 0; i < n; ++i) arr[i] = {nums[i], cost[i]};
            sort(arr.begin(), arr.end());
            vector<ll> f(n + 1), g(n + 1);
            for (int i = 1; i <= n; ++i) {
                auto [a, b] = arr[i - 1];
                f[i] = f[i - 1] + 1ll * a * b;
                g[i] = g[i - 1] + b;
            }
            ll ans = 1e18;
            for (int i = 1; i <= n; ++i) {
                auto [a, _] = arr[i - 1];
                ll l = 1ll * a * g[i - 1] - f[i - 1];
                ll r = f[n] - f[i] - 1ll * a * (g[n] - g[i]);
                ans = min(ans, l + r);
            }
            return ans;
        }
    };
    
  • 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
    
    
  • func minCost(nums []int, cost []int) int64 {
    	n := len(nums)
    	type pair struct{ a, b int }
    	arr := make([]pair, n)
    	for i, a := range nums {
    		b := cost[i]
    		arr[i] = pair{a, b}
    	}
    	sort.Slice(arr, func(i, j int) bool { return arr[i].a < arr[j].a })
    	f := make([]int, n+1)
    	g := make([]int, n+1)
    	for i := 1; i <= n; i++ {
    		a, b := arr[i-1].a, arr[i-1].b
    		f[i] = f[i-1] + a*b
    		g[i] = g[i-1] + b
    	}
    	var ans int64 = 1e18
    	for i := 1; i <= n; i++ {
    		a := arr[i-1].a
    		l := a*g[i-1] - f[i-1]
    		r := f[n] - f[i] - a*(g[n]-g[i])
    		ans = min(ans, int64(l+r))
    	}
    	return ans
    }
    
    func min(a, b int64) int64 {
    	if a < b {
    		return a
    	}
    	return b
    }
    
  • impl Solution {
        #[allow(dead_code)]
        pub fn min_cost(nums: Vec<i32>, cost: Vec<i32>) -> i64 {
            let mut zip_vec: Vec<_> = nums.into_iter().zip(cost.into_iter()).collect();
    
            // Sort the zip vector based on nums
            zip_vec.sort_by(|lhs, rhs| {
                lhs.0.cmp(&rhs.0)
            });
    
            let (nums, cost): (Vec<i32>, Vec<i32>) = zip_vec.into_iter().unzip();
    
            let mut sum: i64 = 0;
            for &c in &cost {
                sum += c as i64 ;
            }
            let middle_cost = (sum + 1) / 2;
            let mut cur_sum: i64 = 0;
            let mut i = 0;
            let n = nums.len();
    
            while i < n {
                if cost[i] as i64 + cur_sum >= middle_cost {
                    break;
                }
                cur_sum += cost[i] as i64;
                i += 1;
            }
            
            Self::compute_manhattan_dis(&nums, &cost, nums[i])
        }
    
        #[allow(dead_code)]
        fn compute_manhattan_dis(v: &Vec<i32>, c: &Vec<i32>, e: i32) -> i64 {
            let mut ret = 0;
            let n = v.len();
    
            for i in 0..n {
                if v[i] == e {
                    continue;
                }
                ret += (v[i] - e).abs() as i64 * c[i] as i64;
            }
    
            ret
        }
    }
    

Explain:

nope.

Complexity:

  • Time complexity : O(n).
  • Space complexity : O(n).

All Problems

All Solutions