2448. Minimum Cost to Make Array Equal

HardGreedyArrayBinary SearchPrefix SumSorting
Leetcode Link

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:

  1. We zip and sort nums and cost together based on the nums values. This pairs each element of nums with its corresponding cost.
  2. We prepare prefix sums for both nums multiplied by cost (f) and for cost alone (g) which will help us calculate the cost with better efficiency.
  3. 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.
  4. 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 in nums 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

How many times is a tree node visited in a depth first search?

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:

  1. Sorting with Zip: The zip function is used to combine nums and cost into a single list of tuples. This list is then sorted based on the nums values using Python's sorted() 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).

  2. Prefix Sums: Two types of prefix sums (f and g) are utilized.

    • f represents the sum of elements of nums each multiplied by its corresponding cost up to the current index. This is calculated as f[i] = f[i - 1] + a * b, where a is the value in nums and b is the value in cost for the current element.
    • g is the sum of the cost 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.

  3. 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 to a, and f[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 from nums[i] onwards, and a * (g[n] - g[i]) subtracts the excess, similar to the left part calculation.

  4. Finding the Minimum: The variable ans is initialized with the value inf (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 updates ans to be the minimum between the current ans and the newly calculated total cost (l + r).

  5. 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following array represent a max heap?

Example 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:

  1. Sorting with Zip: Pairing and sorting based on nums values gives us: sorted_pair = [(1, 2), (2, 3), (3, 4), (4, 1)]

  2. Prefix Sums: For f (cumulative sum of nums times cost), 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 of cost), we get: g[0] = 2 g[1] = g[0] + 3 = 5 g[2] = g[1] + 4 = 9 g[3] = g[2] + 1 = 10

  3. Dynamic Calculation of Costs: We consider each element in nums as the target. For example:

    • Using 1 as the target, the cost to increase is 0 (since it's already the lowest): l = 1 * g[0] - f[0] = 0 The cost to decrease 2, 3, and 4 to 1: r = f[3] - f[0] - 1 * (g[3] - g[0]) = 22 - 0 - 1 * (8) = 14 Total cost for target 1 is then l + r = 0 + 14 = 14.

    • Using 2 as the target, we compute l with elements to the left: l = 2 * g[0] - f[0] = 2 * 2 - 2 = 2 Compute r for elements to the right: r = f[3] - f[1] - 2 * (g[3] - g[1]) = 24 - 8 - 2 * (5) = 6 Total cost for target 2 is l + r = 2 + 6 = 8.

    • Similarly, we would compute for targets 3 and 4.

  4. Finding the Minimum: Initialise ans = inf. After computing l + r for all possible targets, we'd find ans is minimum for target 2 at a cost of 8.

  5. Returning the Result: The minimum cost found for equalizing all elements to 2 is 8, 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

What are the most two important steps in writing a depth first search function? (Select 2)

Time and Space Complexity

Time Complexity

The time complexity of the given code can be broken down into a few components:

  1. Sorting the combined list of nums and cost: This is done using the sorted() function, which typically employs the Timsort algorithm, having a time complexity of O(n log n) where n is the length of the list to be sorted.

  2. Populating the f and g arrays: The two arrays are filled by iterating over arr once, which has n elements. The operations within the loop are constant time, making this step take O(n) time.

  3. Calculating the minimum cost ans: This involves iterating over each element in arr and performing constant time operations, thus taking O(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:

  1. The arr list, which stores the sorted nums and cost, taking O(n) space.

  2. The f and g arrays, each of which has n + 1 elements, thus together taking 2(n + 1) which is equivalent to O(n) space.

  3. The ans variable, which is constant space O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer technique does Quick Sort use?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 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 When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Binary Search Speedrun

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

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 Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ