# Minimum Cost to Equalize Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-cost-to-equalize-array)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-to-equalize-array
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array
---
## Problem
You are given an integer array `nums` and two integers `cost1` and `cost2`. You are allowed to perform **either** of the following operations **any** number of times:

* Choose an index `i` from `nums` and **increase** `nums[i]` by `1` for a cost of `cost1`.
* Choose two **different** indices `i`, `j`, from `nums` and **increase** `nums[i]` and `nums[j]` by `1` for a cost of `cost2`.

Return the **minimum** **cost** required to make all elements in the array **equal**_._ 

Since the answer may be very large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** nums = \[4,1\], cost1 = 5, cost2 = 2

**Output:** 15

**Explanation:** 

The following operations can be performed to make the values equal:

* Increase `nums[1]` by 1 for a cost of 5\. `nums` becomes `[4,2]`.
* Increase `nums[1]` by 1 for a cost of 5\. `nums` becomes `[4,3]`.
* Increase `nums[1]` by 1 for a cost of 5\. `nums` becomes `[4,4]`.

The total cost is 15.

**Example 2:**

**Input:** nums = \[2,3,3,3,5\], cost1 = 2, cost2 = 1

**Output:** 6

**Explanation:** 

The following operations can be performed to make the values equal:

* Increase `nums[0]` and `nums[1]` by 1 for a cost of 1\. `nums` becomes `[3,4,3,3,5]`.
* Increase `nums[0]` and `nums[2]` by 1 for a cost of 1\. `nums` becomes `[4,4,4,3,5]`.
* Increase `nums[0]` and `nums[3]` by 1 for a cost of 1\. `nums` becomes `[5,4,4,4,5]`.
* Increase `nums[1]` and `nums[2]` by 1 for a cost of 1\. `nums` becomes `[5,5,5,4,5]`.
* Increase `nums[3]` by 1 for a cost of 2\. `nums` becomes `[5,5,5,5,5]`.

The total cost is 6.

**Example 3:**

**Input:** nums = \[3,5,3\], cost1 = 1, cost2 = 3

**Output:** 4

**Explanation:**

The following operations can be performed to make the values equal:

* Increase `nums[0]` by 1 for a cost of 1\. `nums` becomes `[4,5,3]`.
* Increase `nums[0]` by 1 for a cost of 1\. `nums` becomes `[5,5,3]`.
* Increase `nums[2]` by 1 for a cost of 1\. `nums` becomes `[5,5,4]`.
* Increase `nums[2]` by 1 for a cost of 1\. `nums` becomes `[5,5,5]`.

The total cost is 4.

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 106`
* `1 <= cost1 <= 106`
* `1 <= cost2 <= 106`

# Approaches
## Ternary Search on the Target Value
The core idea is that the cost to equalize the array is a function of the target value `T` to which all elements are raised. This cost function, `cost(T)`, is convex (or has a 'bowl' shape). This property allows us to efficiently search for the minimum cost using ternary search.
**Time:** O(N + log(Range)), where N is the number of elements in `nums` and `Range` is the size of the search space for the target value. The O(N) part is for pre-calculating sum, min, and max. The ternary search takes logarithmic time. · **Space:** O(1), as we only use a few variables to store pre-calculated values and search boundaries.
**Pros:** Much more efficient than a linear brute-force search.; Conceptually straightforward for those familiar with ternary search.; Guaranteed to find the optimal solution for convex functions.
**Cons:** Slightly more complex to implement than a simple loop.; Relies on the cost function being convex. While it holds true in this problem, any slight deviation from convexity (e.g., due to floating point issues in other problems, or complex integer arithmetic) could make ternary search unreliable.
### Explanation
First, we handle a simple case: if `2 * cost1 <= cost2`, it's always optimal to use single-increment operations. The cheapest target value is `max(nums)`, so the cost is `sum(max(nums) - nums[i]) * cost1`.

For the more complex case where `2 * cost1 > cost2`, the paired operation is cheaper. The cost to reach a target `T` depends on the total increments needed (`S = n*T - totalSum`) and the maximum increments for any single element (`max_inc = T - minVal`). The cost function `cost(T)` can be shown to be convex. We can find the minimum of this function by performing a ternary search on the target value `T`.

```java
class Solution {
    long cost1, cost2;
    int n;
    long totalSum;
    int minVal;
    final int MOD = 1_000_000_007;

    private long calculateCost(long target) {
        long s = (long)n * target - totalSum;
        long maxInc = target - minVal;
        
        long cost;
        if (2 * maxInc <= s) {
            cost = (s / 2) * cost2 + (s % 2) * cost1;
        } else {
            cost = (s - maxInc) * cost2 + (2 * maxInc - s) * cost1;
        }
        return cost;
    }

    public int minCostToEqualizeArray(int[] nums, int c1, int c2) {
        this.n = nums.length;
        if (n == 1) return 0;

        this.cost1 = c1;
        this.cost2 = c2;

        long maxVal = 0;
        minVal = Integer.MAX_VALUE;
        totalSum = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
            minVal = Math.min(minVal, num);
            totalSum += num;
        }

        if (2 * this.cost1 <= this.cost2) {
            long totalIncrements = maxVal * n - totalSum;
            return (int)((totalIncrements * this.cost1) % MOD);
        }

        long low = maxVal;
        long high = maxVal + 2 * 1000000 + 7; // A sufficiently large upper bound
        long minCost = Long.MAX_VALUE;

        while (low <= high) {
            long m1 = low + (high - low) / 3;
            long m2 = high - (high - low) / 3;
            if (m1 >= m2) break;
            long cost_m1 = calculateCost(m1);
            long cost_m2 = calculateCost(m2);
            if (cost_m1 < cost_m2) {
                minCost = Math.min(minCost, cost_m1);
                high = m2 - 1;
            } else {
                minCost = Math.min(minCost, cost_m2);
                low = m1 + 1;
            }
        }
        minCost = Math.min(minCost, calculateCost(low));
        if(low < high) minCost = Math.min(minCost, calculateCost(high));

        return (int)(minCost % MOD);
    }
}
```
### Algorithm
*   **Handle Simple Case:** If performing two single-increment operations is cheaper or equal to one double-increment operation (`2 * cost1 <= cost2`), it's always optimal to only use single increments. The target value should be the minimum possible, which is `max(nums)`. The total cost is `sum(max(nums) - nums[i]) * cost1`.
*   **Convex Cost Function:** For the main case (`2 * cost1 > cost2`), the cost to make all elements equal to a target value `T` can be modeled as a function `cost(T)`. This function is convex, meaning it has a single minimum. This property is ideal for ternary search.
*   **Define Search Range:** We need to find the optimal `T`. The minimum possible `T` is `max(nums)`. The cost will eventually increase as `T` grows very large. We can set a safe upper bound for our search, for example, `max(nums) + 2 * 10^6`.
*   **Ternary Search Execution:** We apply ternary search on the range of `T`. In each step, we take two midpoints, `m1` and `m2`, and evaluate `cost(m1)` and `cost(m2)`. By comparing these costs, we can eliminate one-third of the search space.
*   **Cost Calculation:** A helper function, `calculateCost(T)`, is needed. It computes the cost for a given target `T` by determining the total increments (`S`) and the maximum increments for any single element (`max_inc`), and then applying the optimal strategy of using paired (`cost2`) and single (`cost1`) operations.
*   **Result:** The search continues until the range is small enough. The minimum cost found during the search is the answer.

## Analytical O(N) Solution
This approach involves a deeper mathematical analysis of the cost function `cost(T)`. By understanding its properties, we can directly calculate the region where the minimum cost will occur, avoiding a search altogether. This leads to a highly efficient O(N) solution.
**Time:** O(N), dominated by the single pass to compute `minVal`, `maxVal`, and `totalSum`. The rest of the logic runs in constant time. · **Space:** O(1), as it only requires a constant amount of extra space.
**Pros:** The most efficient solution with O(N) time complexity.; Avoids searching by directly computing the optimal target candidates.; Very fast and does not depend on the range of values in `nums` for its performance beyond the initial pass.
**Cons:** Requires a more involved mathematical analysis of the cost function, which can be complex to derive correctly.; The implementation logic is more intricate and has more cases to consider than the ternary search approach.
### Explanation
The cost function `cost(T)` is piecewise. The behavior of the function changes at a critical point `T_crit` where `2 * max_inc` (maximum increments for one element) equals `S` (total increments).

`2 * (T - minVal) = n * T - totalSum`
`=> (n - 2) * T = totalSum - 2 * minVal`
`=> T_crit = (totalSum - 2 * minVal) / (n - 2)` (for `n > 2`)

By analyzing the slope of `cost(T)` before and after this critical point, we can determine where the minimum lies without searching.

```java
class Solution {
    long cost1, cost2;
    int n;
    long totalSum;
    int minVal;
    final int MOD = 1_000_000_007;

    private long calculateCost(long target) {
        if (target < minVal) return Long.MAX_VALUE;
        long s = (long)n * target - totalSum;
        long maxInc = target - minVal;
        
        long cost;
        if (2 * maxInc <= s) {
            cost = (s / 2) * cost2 + (s % 2) * cost1;
        } else {
            cost = (s - maxInc) * cost2 + (2 * maxInc - s) * cost1;
        }
        return cost;
    }

    public int minCostToEqualizeArray(int[] nums, int c1, int c2) {
        this.n = nums.length;
        if (n == 1) return 0;

        this.cost1 = c1;
        this.cost2 = c2;

        long maxVal = 0;
        minVal = Integer.MAX_VALUE;
        totalSum = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
            minVal = Math.min(minVal, num);
            totalSum += num;
        }

        if (2 * this.cost1 <= this.cost2) {
            long totalIncrements = maxVal * n - totalSum;
            return (int)((totalIncrements * this.cost1) % MOD);
        }

        // Case: 2 * cost1 > cost2
        // Check if cost function is always non-decreasing for T >= maxVal
        if (n <= 2 || (long)(n - 1) * this.cost2 >= (long)(n - 2) * this.cost1) {
            return (int)(calculateCost(maxVal) % MOD);
        } else {
            // Cost function decreases before T_crit, then increases.
            long t_crit_num = totalSum - 2L * minVal;
            long t_crit_den = n - 2;
            
            long t_crit = t_crit_num / t_crit_den;

            long cand_t = Math.max(maxVal, t_crit);
            
            long cost_cand1 = calculateCost(cand_t);
            long cost_cand2 = calculateCost(cand_t + 1);
            
            return (int)(Math.min(cost_cand1, cost_cand2) % MOD);
        }
    }
}
```
### Algorithm
*   **Initial Setup:** The simple case (`2 * cost1 <= cost2`) and edge cases (`n=1`) are handled as before. An O(N) pass is used to find `minVal`, `maxVal`, and `totalSum`.
*   **Analyze Cost Function Slope:** The key insight is to analyze the slope of the cost function `cost(T)`. The function's behavior depends on a critical point `T_crit` where `2 * max_inc ≈ S`. 
    *   For `T < T_crit`, the slope of `cost(T)` is approximately constant, determined by `(n-1)*cost2 - (n-2)*cost1`.
    *   For `T > T_crit`, the slope is always positive.
*   **Two Scenarios:**
    1.  **Non-decreasing Cost:** If the slope for `T < T_crit` is non-negative (i.e., `(n-1)*cost2 >= (n-2)*cost1`), the cost function is non-decreasing for all `T >= maxVal`. Thus, the minimum cost is achieved at the smallest possible target, `T = maxVal`.
    2.  **Decreasing then Increasing Cost:** If the slope is negative, `cost(T)` first decreases and then increases after passing `T_crit`. The minimum must occur at or very near `T_crit`. We can calculate `T_crit = (totalSum - 2*minVal) / (n-2)`.
*   **Direct Calculation:** Instead of searching, we directly identify the candidate(s) for the optimal `T`. The optimal `T` will be `max(maxVal, floor(T_crit))`. Due to the discrete nature of the problem, we check this candidate and its successor, `T_cand+1`, to find the true minimum.
*   **Final Result:** The minimum of the costs calculated for these few candidates is the answer.