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.
This approach focuses on sorting the array first and then attempting to make all elements equal to a common value using either single or double increments wisely.
Once sorted, the cost to increase the lower elements to any higher level can be estimated, allowing the application of strategic increments using cost1 and cost2.
This Python solution sorts the input array, then calculates and applies the required increment combinations to ensure all elements become equal, opting for the most cost-effective method (single or pair increment). Note: The code needs adjustment to correctly implement the two-increment logic after refining the increment check conditions.
Python
Time Complexity: O(n log n) due to sorting, where n is the length of nums.
Space Complexity: O(1) auxiliary space beyond input/output storage.
This approach leverages binary search to identify the minimum target value that can make all elements equal at the lowest cost. Calculate the cost for making all numbers equal to each potential target and choose the one with the minimal cost.
In this solution, we use a binary search to find the optimal target value. For each target value, we compute the cost to make all array elements equal to it. If costs improve on either side, we alter our search range.
Python
Time Complexity: O(n log(max(nums) - min(nums))) due to binary search across possible target values with constant-time operations over n.
Space Complexity: O(1) as only finite extra variables are used.
This method involves considering each potential final value for the array elements. For each value, calculate the total cost to make all elements equal to it. This approach can be optimized by limiting the search space using sorted order or range of existing numbers.
This solution iterates over potential target values from the minimum to the maximum element in the array. For each target value, it calculates the total cost to convert every element to this target using the given cost rules.
Time Complexity: O((max-min) * n), where n is the length of nums.
Space Complexity: O(1), as we only store a constant number of variables.
Considering the monotonically increasing nature of costs with incrementing values, a binary search over the possible target values might efficiently minimize the transformation cost. This approach utilizes the sorted list of elements and calculates for mean or median value transitions to guide search space reduction.
The solution uses binary search across sorted array values, determining cost minima by observing cost changes over mid-point transitions and honing into the most cost-effective central position.
C++
JavaScript
Time Complexity: O(n log(max - min)), encompassing the search and cost computation per target.
Space Complexity: O(1), relying only on existing input storage range.
| Approach | Complexity |
|---|---|
| Approach 1: Sort and Single Pass Increment | Time Complexity: O(n log n) due to sorting, where n is the length of nums. |
| Approach 2: Binary Search on Result Value | Time Complexity: O(n log(max(nums) - min(nums))) due to binary search across possible target values with constant-time operations over n. |
| Brute Force Evaluation of Target Values | Time Complexity: O((max-min) * n), where n is the length of nums. |
| Binary Search on Possible Target Values | Time Complexity: O(n log(max - min)), encompassing the search and cost computation per target. |
| 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 |
3139. Minimum Cost to Equalize Array | Cases | Reduce values in Pairs Trick | Greedy | Math • Aryan Mittal • 5,102 views views
Watch 6 more video solutions →Practice Minimum Cost to Equalize Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor