# Minimum Cost to Make Array Equal
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-cost-to-make-array-equal)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-to-make-array-equal
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [HashedIn](https://scaleengineer.com/companies/hashedin)
---
## 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`
* Test cases are generated in a way that the output doesn't exceed 253\-1

# Approaches
## Brute Force Iteration
The core idea is to find the final equal value that all elements in `nums` will be converted to. A crucial observation is that this optimal target value must lie within the range of the minimum and maximum values present in the `nums` array. Any target value outside this range would result in a higher cost. Therefore, we can simply iterate through every possible integer target value from `min(nums)` to `max(nums)`, calculate the total cost for each target, and find the minimum one.
**Time:** O(N * M), where N is the length of the arrays and M is the difference between the maximum and minimum values in `nums`. This is because we have a nested loop structure: the outer loop runs M times and the inner loop runs N times. · **Space:** O(1), as we only use a few variables to store state, regardless of the input size.
**Pros:** Simple to conceptualize and implement.
**Cons:** Extremely inefficient for large ranges of `nums` values, leading to a Time Limit Exceeded error on most platforms.
### Explanation
This method involves a straightforward check of all potential candidates for the final value.

```java
class Solution {
    public long minCost(int[] nums, int[] cost) {
        long minCost = Long.MAX_VALUE;
        int minVal = Integer.MAX_VALUE;
        int maxVal = Integer.MIN_VALUE;
        for (int num : nums) {
            minVal = Math.min(minVal, num);
            maxVal = Math.max(maxVal, num);
        }

        for (int target = minVal; target <= maxVal; target++) {
            long currentCost = 0;
            for (int i = 0; i < nums.length; i++) {
                currentCost += (long) Math.abs(nums[i] - target) * cost[i];
            }
            minCost = Math.min(minCost, currentCost);
        }
        return minCost;
    }
}
```
### Algorithm
- First, determine the search space by finding the minimum (`minVal`) and maximum (`maxVal`) elements in the `nums` array.
- Initialize a variable `minCost` to a very large value to store the minimum cost found so far.
- Iterate through each integer `target` from `minVal` to `maxVal`.
- For each `target`, calculate the `currentCost` required to make all elements in `nums` equal to `target`. This is done by summing up `abs(nums[i] - target) * cost[i]` for all `i`.
- Compare `currentCost` with `minCost` and update `minCost` if `currentCost` is smaller.
- After checking all possible targets, `minCost` will hold the minimum possible cost.

## Binary Search on the Cost Function
The total cost, as a function of the target value `x`, is `f(x) = sum(|nums[i] - x| * cost[i])`. This function is a sum of V-shaped functions, which results in a convex (U-shaped) function. A key property of a convex function is that it has a single minimum. This allows us to use a binary search-like approach to find this minimum efficiently. By comparing the costs at two nearby points, we can determine which direction to search in, effectively halving the search space in each step.
**Time:** O(N * log M), where N is the array length and M is the search range size (e.g., 10^6). The binary search performs `log M` iterations, and each iteration calls `calculateCost`, which takes O(N) time. · **Space:** O(1), as the search is done in-place without requiring extra space proportional to the input size.
**Pros:** Much more efficient than brute force.; Guaranteed to find the minimum for a convex function.
**Cons:** The cost function is calculated repeatedly, which might be less efficient than a single-pass algorithm after sorting.
### Explanation
Instead of a linear scan, we can intelligently narrow down the search space for the optimal target value.

```java
class Solution {
    public long minCost(int[] nums, int[] cost) {
        int low = 1;
        int high = 1000000; // From constraints
        long ans = Long.MAX_VALUE;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            long cost1 = calculateCost(nums, cost, mid);
            long cost2 = calculateCost(nums, cost, mid + 1);
            
            ans = Math.min(cost1, cost2);

            if (cost1 < cost2) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    private long calculateCost(int[] nums, int[] cost, int target) {
        long totalCost = 0L;
        for (int i = 0; i < nums.length; i++) {
            totalCost += (long) Math.abs(nums[i] - target) * cost[i];
        }
        return totalCost;
    }
}
```
### Algorithm
- Define the search range `[low, high]` for the target value. A safe range is from 1 to 1,000,000, as given by the problem constraints.
- Create a helper function, `calculateCost(target)`, which takes a target value and computes the total cost to make all `nums` elements equal to it in O(N) time.
- Use a `while` loop to perform the binary search as long as `low <= high`.
- In each iteration, calculate a midpoint `mid`.
- Compare the cost at `mid` with the cost at `mid + 1`. Let them be `cost1` and `cost2`.
- If `cost1 < cost2`, it implies the minimum is located at or to the left of `mid`. Thus, we can discard the right half by setting `high = mid - 1`.
- If `cost1 >= cost2`, the minimum is at or to the right of `mid + 1`. We discard the left half by setting `low = mid + 1`.
- Keep track of the minimum cost found during this process. The final answer will be the minimum of all `cost1` and `cost2` values computed.

## Optimal Solution using Weighted Median
This problem can be elegantly solved by identifying it as a search for the weighted median. The expression `sum(cost[i] * |nums[i] - x|)` is minimized when `x` is the weighted median of the numbers in `nums`, where `cost[i]` are the weights. The weighted median is the value that partitions the sorted weights into two equal halves. Once we find this median value, we can calculate the minimum cost.
**Time:** O(N log N), dominated by the sorting step. The subsequent passes to find the median and calculate the final cost take O(N) time. · **Space:** O(N), required to store the pairs of `(num, cost)` for sorting.
**Pros:** This is the most efficient and standard approach for this type of problem.; It directly identifies the optimal target value with mathematical reasoning.
**Cons:** Requires extra space to store pairs for sorting.
### Explanation
The most efficient approach involves sorting the numbers and finding the point where the cumulative cost (weight) crosses the halfway point of the total cost.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public long minCost(int[] nums, int[] cost) {
        int n = nums.length;
        int[][] pairs = new int[n][2];
        long totalWeight = 0;
        for (int i = 0; i < n; i++) {
            pairs[i][0] = nums[i];
            pairs[i][1] = cost[i];
            totalWeight += cost[i];
        }

        Arrays.sort(pairs, Comparator.comparingInt(a -> a[0]));

        long medianNum = -1;
        long cumulativeWeight = 0;
        for (int i = 0; i < n; i++) {
            cumulativeWeight += pairs[i][1];
            if (cumulativeWeight * 2 >= totalWeight) {
                medianNum = pairs[i][0];
                break;
            }
        }

        long minTotalCost = 0;
        for (int i = 0; i < n; i++) {
            minTotalCost += (long) Math.abs(nums[i] - medianNum) * cost[i];
        }

        return minTotalCost;
    }
}
```
### Algorithm
- Create an array of pairs, where each pair contains `(nums[i], cost[i])`.
- Calculate the sum of all costs, let's call it `totalWeight`.
- Sort the array of pairs based on the `nums` values in ascending order.
- Iterate through the sorted pairs and maintain a `cumulativeWeight`. In each step, add the cost of the current pair to `cumulativeWeight`.
- The weighted median is the number from the first pair for which `cumulativeWeight` becomes greater than or equal to half of `totalWeight`. Let this number be `medianNum`.
- The minimum cost is then the total cost to make all elements equal to `medianNum`. Calculate this by summing `abs(nums[i] - medianNum) * cost[i]` for all original `i`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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 ; } };
```

### Python

```python
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

```