Minimum Cost to Equalize Array solution and explanation
4 more videos on this problem
3139. Minimum Cost to Equalize Array | Cases | Reduce values in Pairs Trick | Greedy | MathAryan Mittal · 54:04 · 5K views
3139. Minimum Cost to Equalize Array | Weekly Leetcode 396codingMohan · 1:05:27 · 1K views
3139. Minimum Cost to Equalize Array (Leetcode Hard)Programming Live with Larry · 1:13:04 · 895 views
【每日一题】LeetCode 3139. Minimum Cost to Equalize ArrayHuifeng Guan · 32:53 · 626 views
DECODEDSA#LEVELUP#CONTESTSOL#leetcode#challenge#LC 3139. Minimum Cost to Equalize ArrayDecode · 7:31 · 123 views
The 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
ifromnumsand increasenums[i]by1for a cost ofcost1. - Choose two different indices
i,j, fromnumsand increasenums[i]andnums[j]by1for a cost ofcost2.
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.numsbecomes[4,2]. - Increase
nums[1]by 1 for a cost of 5.numsbecomes[4,3]. - Increase
nums[1]by 1 for a cost of 5.numsbecomes[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]andnums[1]by 1 for a cost of 1.numsbecomes[3,4,3,3,5]. - Increase
nums[0]andnums[2]by 1 for a cost of 1.numsbecomes[4,4,4,3,5]. - Increase
nums[0]andnums[3]by 1 for a cost of 1.numsbecomes[5,4,4,4,5]. - Increase
nums[1]andnums[2]by 1 for a cost of 1.numsbecomes[5,5,5,4,5]. - Increase
nums[3]by 1 for a cost of 2.numsbecomes[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.numsbecomes[4,5,3]. - Increase
nums[0]by 1 for a cost of 1.numsbecomes[5,5,3]. - Increase
nums[2]by 1 for a cost of 1.numsbecomes[5,5,4]. - Increase
nums[2]by 1 for a cost of 1.numsbecomes[5,5,5].
The total cost is 4.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1061 <= cost1 <= 1061 <= cost2 <= 106
Approach overview
Problem 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 1: Approach 1: Sort and Single Pass Increment
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.
def minCost(nums, cost1, cost2):
nums.sort()
n = len(nums)
total_cost = 0
for i in range(n - 1):
difference = nums[i + 1] - nums[i]
increment_needed = difference // 2 * 2 * cost2 + (difference % 2) * cost1
total_cost += increment_needed
return total_cost % (10**9 + 7)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.
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.
Approach 2: Approach 2: Binary Search on Result Value
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.
def minCost(nums, cost1, cost2):
def calculate_cost(target):
cost = 0
for num in nums:
if num < target:
diff = target - num
if diff % 2 == 0:
cost += (diff // 2) * cost2
else:
cost += (diff // 2) * cost2 + cost1
elif num > target:
cost += (num - target) * cost1
return cost
left, right = min(nums), max(nums)
min_total_cost = float('inf')
while left <= right:
mid = (left + right) // 2
cost = calculate_cost(mid)
min_total_cost = min(min_total_cost, cost)
if calculate_cost(mid - 1) < cost:
right = mid - 1
elif calculate_cost(mid + 1) < cost:
left = mid + 1
else:
break
return min_total_cost % (10**9 + 7)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.
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.
Approach 3: Brute Force Evaluation of Target Values
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.
def min_cost_to_equalize(nums, cost1, cost2):
mod = 10**9 + 7
min_value, max_value = min(nums), max(nums)
def cost_to_make_all_equal(target):
cost = 0
for num in nums:
gap = abs(target - num)
cost += (gap * cost1 if gap % 2 != 0 else min(gap * cost1, (gap // 2) * cost2))
return cost % mod
return min(cost_to_make_all_equal(target) for target in range(min_value, max_value + 1))public class EqualizeArray {
public int minCostToEqualize(int[] nums, int cost1, int cost2) {
int mod = 1000000007;
int minVal = Arrays.stream(nums).min().getAsInt();
int maxVal = Arrays.stream(nums).max().getAsInt();
int minCost = Integer.MAX_VALUE;
for (int target = minVal; target <= maxVal; target++) {
long cost = 0;
for (int num : nums) {
int gap = Math.abs(target - num);
cost += (gap % 2 != 0 ? gap * cost1 : Math.min(gap * cost1, (gap / 2) * cost2));
}
minCost = Math.min(minCost, (int)(cost % mod));
}
return minCost;
}
}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.
Approach 4: Binary Search on Possible Target Values
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.
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int minCostToEqualize(vector<int>& nums, int cost1, int cost2) {
int n = nums.size();
int mod = 1000000007;
sort(nums.begin(), nums.end());
int low = nums[0], high = nums[n-1];
auto compute_cost = [&](int target) {
long long cost = 0;
for(int num : nums) {
int gap = abs(target - num);
cost += (gap * cost1 < (gap / 2) * cost2) ? (gap * cost1) : ((gap / 2) * cost2);
}
return cost % mod;
};
while (low < high) {
int mid = low + (high - low) / 2;
long long costMid = compute_cost(mid);
long long costMidPlusOne = compute_cost(mid + 1);
if (costMid > costMidPlusOne) {
low = mid + 1;
} else {
high = mid;
}
}
return compute_cost(low);
}function minCostToEqualize(nums, cost1, cost2) {
nums.sort((a, b) => a - b);
const mod = 1e9 + 7;
let low = nums[0], high = nums[nums.length - 1];
const computeCost = (target) => {
let cost = 0;
for (let num of nums) {
let gap = Math.abs(target - num);
cost += Math.min(gap * cost1, Math.floor(gap / 2) * cost2);
}
return cost % mod;
};
while (low < high) {
let mid = Math.floor((low + high) / 2);
let costMid = computeCost(mid);
let costMidPlusOne = computeCost(mid + 1);
if (costMid > costMidPlusOne) {
low = mid + 1;
} else {
high = mid;
}
}
return computeCost(low);
}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.
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.
Complexity comparison
| 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. |
Complexity analysis
| 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 |
Frequently asked questions
Is Minimum Cost to Equalize Array easy or hard?
Minimum Cost to Equalize Array is classified as a Hard problem on LeetCode with an acceptance rate around 18%. The challenge comes from modeling the cost function correctly and recognizing when greedy pairing and binary search can minimize the total cost.
Minimum Cost to Equalize Array Python/Java solution
Python and Java implementations typically iterate through the array to compute required increments and evaluate the cheapest mix of single and paired operations. Many solutions combine this cost calculation with binary search on the target value to achieve O(n log M) performance.
How to solve Minimum Cost to Equalize Array in O(n)?
A near-linear evaluation can be achieved once the target value is known. For a fixed target T, iterate through the array to compute the number of increments required for each element and greedily apply paired increments when cost2 is cheaper than two single operations. The overall algorithm becomes O(n) per evaluation step.
What is the best approach for Minimum Cost to Equalize Array?
The most effective approach uses greedy cost evaluation combined with binary search on the target value. For each candidate target T, compute total increments needed and determine how many can be paired using the double-increment operation. This reduces the search space and runs in O(n log M) time with O(1) extra space.
Is Minimum Cost to Equalize Array asked at Google/Amazon/Meta?
Problems involving cost minimization with paired operations and target equalization appear frequently in interviews at companies like Google, Amazon, and Meta. Variations often test greedy reasoning, enumeration of target values, and optimization using binary search.
What data structure is used in Minimum Cost to Equalize Array?
The solution mainly uses a simple array and arithmetic calculations. Sorting may be applied in some approaches, while the optimized solution relies on greedy reasoning and binary search rather than complex data structures.
What is the time complexity of Minimum Cost to Equalize Array?
The optimized solution runs in O(n log M) time, where n is the array size and M is the range of possible target values. Each binary search step scans the array once to compute required increments and evaluate the minimum cost. Space complexity remains O(1).