Minimum Cost to Equalize Array

Hard

#2789Time: 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.

Patterns

Greedy Enumeration

Data structures

Array

Prompt

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 10⁹ + 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 <= 10⁵
1 <= nums[i] <= 10⁶
1 <= cost1 <= 10⁶
1 <= cost2 <= 10⁶

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    long cost1, cost2;3    int n;4    long totalSum;5    int minVal;6    final int MOD = 1_000_000_007;7 8    private long calculateCost(long target) {9        long s = (long)n * target - totalSum;10        long maxInc = target - minVal;11        12        long cost;13        if (2 * maxInc <= s) {14            cost = (s / 2) * cost2 + (s % 2) * cost1;15        } else {16            cost = (s - maxInc) * cost2 + (2 * maxInc - s) * cost1;17        }18        return cost;19    }20 21    public int minCostToEqualizeArray(int[] nums, int c1, int c2) {22        this.n = nums.length;23        if (n == 1) return 0;24 25        this.cost1 = c1;26        this.cost2 = c2;27 28        long maxVal = 0;29        minVal = Integer.MAX_VALUE;30        totalSum = 0;31        for (int num : nums) {32            maxVal = Math.max(maxVal, num);33            minVal = Math.min(minVal, num);34            totalSum += num;35        }36 37        if (2 * this.cost1 <= this.cost2) {38            long totalIncrements = maxVal * n - totalSum;39            return (int)((totalIncrements * this.cost1) % MOD);40        }41 42        long low = maxVal;43        long high = maxVal + 2 * 1000000 + 7; // A sufficiently large upper bound44        long minCost = Long.MAX_VALUE;45 46        while (low <= high) {47            long m1 = low + (high - low) / 3;48            long m2 = high - (high - low) / 3;49            if (m1 >= m2) break;50            long cost_m1 = calculateCost(m1);51            long cost_m2 = calculateCost(m2);52            if (cost_m1 < cost_m2) {53                minCost = Math.min(minCost, cost_m1);54                high = m2 - 1;55            } else {56                minCost = Math.min(minCost, cost_m2);57                low = m1 + 1;58            }59        }60        minCost = Math.min(minCost, calculateCost(low));61        if(low < high) minCost = Math.min(minCost, calculateCost(high));62 63        return (int)(minCost % MOD);64    }65}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    long cost1, cost2;3    int n;4    long totalSum;5    int minVal;6    final int MOD = 1_000_000_007;7 8    private long calculateCost(long target) {9        if (target < minVal) return Long.MAX_VALUE;10        long s = (long)n * target - totalSum;11        long maxInc = target - minVal;12        13        long cost;14        if (2 * maxInc <= s) {15            cost = (s / 2) * cost2 + (s % 2) * cost1;16        } else {17            cost = (s - maxInc) * cost2 + (2 * maxInc - s) * cost1;18        }19        return cost;20    }21 22    public int minCostToEqualizeArray(int[] nums, int c1, int c2) {23        this.n = nums.length;24        if (n == 1) return 0;25 26        this.cost1 = c1;27        this.cost2 = c2;28 29        long maxVal = 0;30        minVal = Integer.MAX_VALUE;31        totalSum = 0;32        for (int num : nums) {33            maxVal = Math.max(maxVal, num);34            minVal = Math.min(minVal, num);35            totalSum += num;36        }37 38        if (2 * this.cost1 <= this.cost2) {39            long totalIncrements = maxVal * n - totalSum;40            return (int)((totalIncrements * this.cost1) % MOD);41        }42 43        // Case: 2 * cost1 > cost244        // Check if cost function is always non-decreasing for T >= maxVal45        if (n <= 2 || (long)(n - 1) * this.cost2 >= (long)(n - 2) * this.cost1) {46            return (int)(calculateCost(maxVal) % MOD);47        } else {48            // Cost function decreases before T_crit, then increases.49            long t_crit_num = totalSum - 2L * minVal;50            long t_crit_den = n - 2;51            52            long t_crit = t_crit_num / t_crit_den;53 54            long cand_t = Math.max(maxVal, t_crit);55            56            long cost_cand1 = calculateCost(cand_t);57            long cost_cand2 = calculateCost(cand_t + 1);58            59            return (int)(Math.min(cost_cand1, cost_cand2) % MOD);60        }61    }62}

Complexity

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.

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem