Watch 7 video solutions for Minimum Cost to Equalize Array, a hard level problem involving Array, Greedy, Enumeration. This walkthrough by Aryan Mittal has 5,102 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
i from nums and increase nums[i] by 1 for a cost of cost1.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:
nums[1] by 1 for a cost of 5. nums becomes [4,2].nums[1] by 1 for a cost of 5. nums becomes [4,3].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:
nums[0] and nums[1] by 1 for a cost of 1. nums becomes [3,4,3,3,5].nums[0] and nums[2] by 1 for a cost of 1. nums becomes [4,4,4,3,5].nums[0] and nums[3] by 1 for a cost of 1. nums becomes [5,4,4,4,5].nums[1] and nums[2] by 1 for a cost of 1. nums becomes [5,5,5,4,5].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:
nums[0] by 1 for a cost of 1. nums becomes [4,5,3].nums[0] by 1 for a cost of 1. nums becomes [5,5,3].nums[2] by 1 for a cost of 1. nums becomes [5,5,4].nums[2] by 1 for a cost of 1. nums becomes [5,5,5].The total cost is 4.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1061 <= cost1 <= 1061 <= cost2 <= 106Problem Overview: You are given an integer array and two operation costs: increment one element by 1, or increment two different elements by 1 simultaneously. The goal is to make every element equal with the minimum possible total cost.
Approach 1: Brute Force Evaluation of Target Values (O(n * R) time, O(1) space)
The simplest strategy tries every feasible target value T greater than or equal to the current maximum element. For each candidate T, compute how many total increments are needed across the array and decide how many can be paired using the cheaper double-increment operation. The algorithm iterates through the array for every candidate target and calculates the cost directly. This approach demonstrates the mechanics of pairing increments but becomes slow when the search range of possible targets is large.
Approach 2: Sort and Single Pass Increment (O(n log n) time, O(1) space)
Sorting the array reveals how far each element is from the largest value. After sorting, you perform a single pass computing the total number of increments required to reach the target and track how many increments can be paired. The greedy insight is that if cost2 < 2 * cost1, pairing increments across two elements reduces cost; otherwise it is cheaper to apply single increments independently. Sorting simplifies the distribution of increments and makes it easy to reason about the number of pairable operations.
Approach 3: Binary Search on Result Value (O(n log M) time, O(1) space)
Instead of testing every possible target value, binary search the optimal final value T. For each candidate T, iterate through the array to compute required increments and determine the cheapest mix of single and paired operations. Because the cost function behaves monotonically with respect to the target value, binary search quickly narrows the optimal result. This method is common when a problem asks for the minimum cost associated with a monotonic constraint.
Approach 4: Binary Search on Possible Target Values (O(n log M) time, O(1) space)
A refined variation of the previous idea explicitly enumerates candidate targets and uses binary search to minimize cost. Each check computes total increments, counts potential pairs, and evaluates the cost using greedy pairing logic. This approach keeps the implementation simple while still achieving efficient performance for large arrays.
Recommended for interviews: Start by explaining the brute-force evaluation to show you understand how increments and pair operations interact. Then move to the binary-search-based optimization combined with a greedy cost calculation. Interviewers typically expect the optimized binary search + greedy pairing approach because it reduces the search space while keeping the cost evaluation linear. The problem mainly tests reasoning about operations on an array, cost optimization with greedy decisions, and exploring candidate values through enumeration.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Target Evaluation | O(n * R) | O(1) | Understanding cost mechanics and validating logic on small ranges |
| Sort and Single Pass Increment | O(n log n) | O(1) | When sorting simplifies increment distribution and pairing analysis |
| Binary Search on Result Value | O(n log M) | O(1) | Efficient solution for large arrays with wide target ranges |
| Binary Search on Possible Target Values | O(n log M) | O(1) | Clean implementation combining greedy cost evaluation with search |