2448. Minimum Cost to Make Array Equal
Problem Description
In this problem, we are given two arrays nums
and cost
of equal length n
. The nums
array holds the actual values of the elements we must manipulate, and the cost
array indicates how much it costs to increase or decrease an element in the corresponding position of the nums
array by 1
.
Our objective is to make all elements in the nums
array equal to each other by either increasing or decreasing their values. The catch is, every operation has a cost associated with it, based on the cost
array. We want to find the minimum total cost required to achieve this.
The main challenge is to figure out what value we should aim for all elements in the nums
array to reach, and do this as cost-efficient as possible.
Intuition
The solution hinges on finding a target value in the nums
array that minimizes the total cost. Intuitively, aiming for a value too high or too low will not be cost efficient, as it would require more operations for elements that are far from such extremes.
In fact, a good target value can be one of the current elements in the nums
array, since aiming for a value not present may potentially increase the total cost compared to aiming for a value already there.
Sorting the array nums
along with cost
will help us approach this problem methodically. The sorted nature of nums
allows us to consider the pivot elements (target values) one by one and calculate the cost required to make the rest of the elements equal to the pivot.
Here is a step-by-step explanation of how the solution works:
- We zip and sort
nums
andcost
together based on thenums
values. This pairs each element ofnums
with its corresponding cost. - We prepare prefix sums for both
nums
multiplied bycost
(f
) and forcost
alone (g
) which will help us calculate the cost with better efficiency. - We iterate through each possible target value (which are now sorted) and calculate the total cost required for the rest of the array to reach this target value. This is done in two parts:
l
is the total cost to decrease the left part of the array to the current target value.r
is the total cost to increase the right part of the array to the current target value.
- The minimum of these calculated costs (
ans
) for each element being the target is the answer we are seeking. It represents the lowest possible cost to make all elements innums
equal.
The algorithm explores all elements as potential targets and uses cumulative costs to determine the most cost-effective target, hence ensuring we find the minimum total cost to equalize all elements in the given nums
array.
Learn more about Greedy, Binary Search, Prefix Sum and Sorting patterns.
Solution Approach
The implementation of the solution can be broken down into several key steps that leverage algorithms and data structures to find the minimum total cost efficiently:
-
Sorting with Zip: The
zip
function is used to combinenums
andcost
into a single list of tuples. This list is then sorted based on thenums
values using Python'ssorted()
function. Sorting is crucial as it allows us to easily calculate the cost of changing every other element to match a particular element (the pivot). -
Prefix Sums: Two types of prefix sums (
f
andg
) are utilized.f
represents the sum of elements ofnums
each multiplied by its corresponding cost up to the current index. This is calculated asf[i] = f[i - 1] + a * b
, wherea
is the value innums
andb
is the value incost
for the current element.g
is the sum of thecost
elements up to the current index. It is used to calculate the total cost of changing the left or right part of the array to match the current pivot.
-
Dynamic Calculation of Costs: For each potential target value (
a
), the total cost is computed in two halves: the cost to adjust elements to the left (l
) and the cost to adjust elements to the right (r
) of the current index.- The cost to the left is computed as
l = a * g[i - 1] - f[i - 1]
. Here,a * g[i - 1]
estimates the total cost if all elements to the left were increased toa
, andf[i - 1]
subtracts the excess since we've already some elements at the desired value or higher. - The cost to the right is computed as
r = f[n] - f[i] - a * (g[n] - g[i])
. Here,f[n] - f[i]
represents the total sum that would have been without decreasing any elements fromnums[i]
onwards, anda * (g[n] - g[i])
subtracts the excess, similar to the left part calculation.
- The cost to the left is computed as
-
Finding the Minimum: The variable
ans
is initialized with the valueinf
(infinity) to ensure that any real calculated cost will be lower on the first comparison. As the loop iterates through each pivot, the algorithm computes the total cost for each pivot and updatesans
to be the minimum between the currentans
and the newly calculated total cost (l + r
). -
Returning the Result: After the loop, the
ans
value will hold the minimum cost found, and this value is returned as the solution.
This approach is efficient because it cleverly reduces what could be many variable operations into a simple range of sums and differences by leveraging the sorted nature of the array and mathematically sound calculations to find the minimum total cost.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach with the following nums
and cost
arrays:
nums = [3, 1, 2, 4]
cost = [4, 2, 3, 1]
Following the solution approach:
-
Sorting with Zip: Pairing and sorting based on
nums
values gives us:sorted_pair = [(1, 2), (2, 3), (3, 4), (4, 1)]
-
Prefix Sums: For
f
(cumulative sum ofnums
timescost
), we compute:f[0] = 1 * 2 = 2
f[1] = f[0] + 2 * 3 = 8
f[2] = f[1] + 3 * 4 = 20
f[3] = f[2] + 4 * 1 = 24
For
g
(cumulative sum ofcost
), we get:g[0] = 2
g[1] = g[0] + 3 = 5
g[2] = g[1] + 4 = 9
g[3] = g[2] + 1 = 10
-
Dynamic Calculation of Costs: We consider each element in
nums
as the target. For example:-
Using
1
as the target, the cost to increase is0
(since it's already the lowest):l = 1 * g[0] - f[0] = 0
The cost to decrease2
,3
, and4
to1
:r = f[3] - f[0] - 1 * (g[3] - g[0]) = 22 - 0 - 1 * (8) = 14
Total cost for target1
is thenl + r = 0 + 14 = 14
. -
Using
2
as the target, we computel
with elements to the left:l = 2 * g[0] - f[0] = 2 * 2 - 2 = 2
Computer
for elements to the right:r = f[3] - f[1] - 2 * (g[3] - g[1]) = 24 - 8 - 2 * (5) = 6
Total cost for target2
isl + r = 2 + 6 = 8
. -
Similarly, we would compute for targets
3
and4
.
-
-
Finding the Minimum: Initialise
ans = inf
. After computingl + r
for all possible targets, we'd findans
is minimum for target2
at a cost of8
. -
Returning the Result: The minimum cost found for equalizing all elements to
2
is8
, which is thus the answer to this example problem.
This approach allows us to efficiently determine that the best target element in nums
is 2
, and the minimum total cost required to make all elements in the nums
array equal to 2
is 8
.
Solution Implementation
1class Solution:
2 def min_cost(self, nums, costs):
3 # Combine nums and costs into a list of tuples and sort them by 'nums'
4 num_cost_pairs = sorted(zip(nums, costs))
5 n = len(num_cost_pairs)
6
7 # Prefix sums of costs multiplied by corresponding nums
8 prefix_multiplied_costs = [0] * (n + 1)
9
10 # Prefix sums of costs
11 prefix_costs = [0] * (n + 1)
12
13 # Calculate prefix sums
14 for i in range(1, n + 1):
15 num, cost = num_cost_pairs[i - 1]
16 prefix_multiplied_costs[i] = prefix_multiplied_costs[i - 1] + num * cost
17 prefix_costs[i] = prefix_costs[i - 1] + cost
18
19 # Initialize the answer with infinity representing a very high value
20 answer = float('inf')
21
22 # Calculate the minimum cost
23 for i in range(1, n + 1):
24 # Choose the ith element as the 'pivot' number
25 pivot = num_cost_pairs[i - 1][0]
26
27 # Left part: calculate the total cost for numbers before the 'pivot' number
28 left = pivot * prefix_costs[i - 1] - prefix_multiplied_costs[i - 1]
29
30 # Right part: calculate the total cost for numbers after the 'pivot' number
31 right = prefix_multiplied_costs[n] - prefix_multiplied_costs[i] - pivot * (prefix_costs[n] - prefix_costs[i])
32
33 # Update the answer with the minimum sum of left and right parts
34 answer = min(answer, left + right)
35
36 # Return the minimum cost
37 return answer
38
1import java.util.Arrays;
2
3public class Solution {
4
5 // Method to calculate the minimum cost of manipulating numbers
6 public long minCost(int[] nums, int[] costs) {
7 int length = nums.length; // Get the length of the array
8
9 // Create a new two-dimensional array to hold numbers and their corresponding costs
10 int[][] pairedArray = new int[length][2];
11 for (int i = 0; i < length; ++i) {
12 pairedArray[i] = new int[]{nums[i], costs[i]};
13 }
14
15 // Sort the paired array based on the numbers
16 Arrays.sort(pairedArray, (firstPair, secondPair) -> firstPair[0] - secondPair[0]);
17
18 // Initialize prefix sums array for numbers multiplied by their cost (f)
19 // and another for the costs (g)
20 long[] prefixSumProduct = new long[length + 1];
21 long[] prefixSumCost = new long[length + 1];
22
23 // Calculate prefix sums
24 for (int i = 1; i <= length; ++i) {
25 long number = pairedArray[i - 1][0];
26 long cost = pairedArray[i - 1][1];
27 prefixSumProduct[i] = prefixSumProduct[i - 1] + number * cost;
28 prefixSumCost[i] = prefixSumCost[i - 1] + cost;
29 }
30
31 long minimumCost = Long.MAX_VALUE; // Variable to store the minimum cost
32
33 // Calculate minimum total cost of all number manipulation operations
34 for (int i = 1; i <= length; ++i) {
35 long number = pairedArray[i - 1][0];
36 long leftCost = number * prefixSumCost[i - 1] - prefixSumProduct[i - 1];
37 long rightCost = prefixSumProduct[length] - prefixSumProduct[i]
38 - number * (prefixSumCost[length] - prefixSumCost[i]);
39 minimumCost = Math.min(minimumCost, leftCost + rightCost);
40 }
41
42 return minimumCost; // Return the calculated minimum cost
43 }
44}
45
1#include <vector>
2#include <algorithm> // for std::sort
3
4// Alias for long long type
5using ll = long long;
6
7class Solution {
8public:
9 // Function to find the minimum cost needed to make all elements equal
10 long long minCost(vector<int>& nums, vector<int>& cost) {
11 int n = nums.size(); // Get the size of the array
12 // 'pairedArray' holds pairs of number and cost for easy sorting and accessing
13 vector<pair<int, int>> pairedArray(n);
14
15 // Pair each number with its cost
16 for (int i = 0; i < n; ++i) {
17 pairedArray[i] = {nums[i], cost[i]};
18 }
19
20 // Sort the paired array based on the number
21 sort(pairedArray.begin(), pairedArray.end());
22
23 // f[i] will store the total cost up to the i-th element
24 vector<ll> prefixCostSum(n + 1);
25 // g[i] will store the total sum of costs up to the i-th element
26 vector<ll> prefixCountSum(n + 1);
27
28 // Calculate the prefix sums for cost and count
29 for (int i = 1; i <= n; ++i) {
30 auto [number, cost] = pairedArray[i - 1];
31 prefixCostSum[i] = prefixCostSum[i - 1] + static_cast<ll>(number) * cost;
32 prefixCountSum[i] = prefixCountSum[i - 1] + cost;
33 }
34
35 // Initialize answer to a very high value
36 ll answer = 1e18; // Using 1e18 as a representation of infinity
37
38 // Calculate the minimal total cost to make all numbers equal
39 for (int i = 1; i <= n; ++i) {
40 auto [number, _] = pairedArray[i - 1];
41 // Calculate the cost of making all numbers to the left equal to 'number'
42 ll leftCost = static_cast<ll>(number) * prefixCountSum[i - 1] - prefixCostSum[i - 1];
43 // Calculate the cost of making all numbers to the right equal to 'number'
44 ll rightCost = prefixCostSum[n] - prefixCostSum[i] - static_cast<ll>(number) * (prefixCountSum[n] - prefixCountSum[i]);
45 // Update the answer with the minimum cost found so far
46 answer = min(answer, leftCost + rightCost);
47 }
48
49 return answer; // Return the minimal total cost
50 }
51};
52
1// Using an alias for readability
2type Pair = [number, number];
3
4// Function to find the minimum cost needed to make all elements equal
5function minCost(nums: number[], costs: number[]): number {
6 let n: number = nums.length; // Get the size of the array
7 // 'pairedArray' holds pairs of number and cost for easy sorting and accessing
8 let pairedArray: Pair[] = [];
9
10 // Pair each number with its cost and fill the 'pairedArray'
11 for (let i = 0; i < n; i++) {
12 pairedArray.push([nums[i], costs[i]]);
13 }
14
15 // Sort the paired array based on the number
16 pairedArray.sort((a, b) => a[0] - b[0]);
17
18 // prefixCostSum stores the total cost up to the i-th element
19 let prefixCostSum: number[] = new Array(n + 1).fill(0);
20 // prefixCountSum stores the total sum of counts up to the i-th element
21 let prefixCountSum: number[] = new Array(n + 1).fill(0);
22
23 // Calculate the prefix sums for cost and count
24 for (let i = 1; i <= n; i++) {
25 let [number, cost] = pairedArray[i - 1];
26 prefixCostSum[i] = prefixCostSum[i - 1] + number * cost;
27 prefixCountSum[i] = prefixCountSum[i - 1] + cost;
28 }
29
30 // Initialize answer to a very high value
31 let answer: number = Number.MAX_SAFE_INTEGER; // Using maximum safe integer value in JS
32
33 // Calculate the minimal total cost to make all numbers equal
34 for (let i = 1; i <= n; i++) {
35 let [number, _] = pairedArray[i - 1];
36 // Calculate the cost of making all numbers to the left equal to 'number'
37 let leftCost: number = number * prefixCountSum[i - 1] - prefixCostSum[i - 1];
38 // Calculate the cost of making all numbers to the right equal to 'number'
39 let rightCost: number = prefixCostSum[n] - prefixCostSum[i] - number * (prefixCountSum[n] - prefixCountSum[i]);
40 // Update the answer with the minimum cost found so far
41 answer = Math.min(answer, leftCost + rightCost);
42 }
43
44 // Return the minimal total cost
45 return answer;
46}
47
48// Example usage:
49// const numsExample = [1,2,3];
50// const costsExample = [10,10,10];
51// const result = minCost(numsExample, costsExample);
52// console.log(result); // Outputs the minimal cost to console
53
Time and Space Complexity
Time Complexity
The time complexity of the given code can be broken down into a few components:
-
Sorting the combined list of
nums
andcost
: This is done using thesorted()
function, which typically employs the Timsort algorithm, having a time complexity ofO(n log n)
wheren
is the length of the list to be sorted. -
Populating the
f
andg
arrays: The two arrays are filled by iterating overarr
once, which hasn
elements. The operations within the loop are constant time, making this step takeO(n)
time. -
Calculating the minimum cost
ans
: This involves iterating over each element inarr
and performing constant time operations, thus takingO(n)
time.
Overall, the time complexity is dominated by the sorting operation. Hence, the total time complexity of the code is O(n log n)
.
Space Complexity
The space complexity can be attributed to the extra storage used by:
-
The
arr
list, which stores the sortednums
andcost
, takingO(n)
space. -
The
f
andg
arrays, each of which hasn + 1
elements, thus together taking2(n + 1)
which is equivalent toO(n)
space. -
The
ans
variable, which is constant spaceO(1)
.
Therefore, the total space complexity of the code is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.