Minimum Cost to Make Array Equal | HARD OA LEVEL

https://leetcode.com/problems/minimum-cost-to-make-array-equal/

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 <= 10^5
1 <= nums[i], cost[i] <= 10^6

=======================================================================================================================

class Solution {
public:
    long long minCost(vector<int>& nums, vector<int>& cost) {
        int n=nums.size();

        vector<pair<int,int>> arr;
        for(int i=0;i<n;i++){
            arr.push_back({nums[i],cost[i]});
        }
        sort(arr.begin(),arr.end());

        vector<long long> prefix(n,0);
        vector<long long> suffix(n,0);

        long long sum=arr[0].second;
        prefix[0]=0;
        for(int i=1;i<n;i++){
            prefix[i]=prefix[i-1];
            long long diff=arr[i].first-arr[i-1].first;
            prefix[i]+=diff*sum;
            sum+=arr[i].second;
        }

        sum=arr[n-1].second;
        suffix[n-1]=0;
        for(int i=n-2;i>=0;i--){
            suffix[i]=suffix[i+1];
            long long diff=arr[i+1].first-arr[i].first;
            suffix[i]+=diff*sum;
            sum+=arr[i].second;
        }

        long long res=LONG_MAX;
        for(int i=0;i<n;i++){
            res=min(res,(long long)prefix[i]+suffix[i]);
        }
        return res;
    }
};


=======================================================================================================================

BRUTE FORCE

class Solution {
public:
    long long minCost(vector<int>& nums, vector<int>& cost) {
        long long res=LONG_MAX;
        for(int i=0;i<nums.size();i++){
            long long temp=0;
            for(int j=0;j<nums.size();j++){
                if(i!=j){
                    temp+=(long long)abs(nums[i]-nums[j])*(long long)cost[j];
                }
            }
            res=min(temp,res);
        }
        return res;
    }
};