Skip to main content

Prefix Sum

Minimum Cost to Make Array Equal Solution In C++/Java/Python/JS

Problem Description

You are given two 0-indexed arrays nums and cost consisting each of  n positive integers.

You can do the following operation any number of times:

  • Increase or decrease any element of the array nums by 1.

The cost of doing one operation on the ith element is cost[i].

Return the minimum total cost such that all the elements of the array nums become equal.

Example

Example 1:

Input: nums = [1,3,5,2], cost = [2,3,1,14]
Output: 8
Explanation: We can make all the elements equal to 2 in the following way:
- Increase the 0th element one time. The cost is 2.
- Decrease the 1st element one time. The cost is 3.
- Decrease the 2nd element three times. The cost is 1 + 1 + 1 = 3.
The total cost is 2 + 3 + 3 = 8.
It can be shown that we cannot make the array equal with a smaller cost.

Example 2:

Input: nums = [2,2,2,2,2], cost = [4,2,8,1,3]
Output: 0
Explanation: All the elements are already equal, so no operations are needed.

Constraints

  • n == nums.length == cost.length
  • 1 <= n <= 10^5
  • 1 <= nums[i], cost[i] <= 10^6
  • Test cases are generated in a way that the output doesn't exceed 253-1
💡
Try Solving Minimum Cost to Make Array Equal Yourself First !!
Let's dive into the problem "Minimum Cost to Make Array Equal" step by step. We'll begin by exploring the most intuitive Brute Force solution, understanding how it works in detail. Then, we'll gradually improve it by identifying inefficiencies and working toward a more optimized approach. So, grab a pen and paper—let's break down the algorithm together and build up our understanding one layer at a time!

Brute-Force Approach

Intuition

If we break down our problem, we are given two arrays:

  • nums[] representing the values we want to make equal.
  • cost[] representing the cost to increment or decrement each value in nums[].

Our goal is to make all elements in nums[] equal, with the minimum total cost, where changing nums[i] by 1 unit costs cost[i].

Now, if we observe carefully, the first question came to our mind is What number should we make everything equal to? We don’t know the best number ahead of time. So, why not just try every number from the array itself as a potential target? This will ensure that the cost conversion will be 0 for at least one element in array.

So, let’s say we try to make all numbers equal to 5. What would that cost?

For every number in the array, we ask:

“How far is this number from 5?”
“How expensive is it to move it that far?”
Multiply that distance by its cost, and you get the cost for that element.

So, the cost = distance * cost

If we do this for every number in the array, add all those up, and now you know the total cost of making everything equal to 5.

Then, we try the same for all the numbers in array and calculate the total cost for each case. In the end, we just pick the number that gives us the minimum total cost.

For Example let’s say we’re given:

nums = [1, 3, 2]
cost = [1, 2, 1]

This means:

  • Changing nums[0] = 1 by 1 unit costs 1 coin.
  • Changing nums[1] = 3 by 1 unit costs 2 coins.
  • Changing nums[2] = 2 by 1 unit costs 1 coin.

We aim to make all elements in nums equal and spend the least possible cost doing that.

We’ll try each number in nums[] as the potential target.

Try making all numbers equal to 1:

  • 1 → 1: distance = 0 → cost = 0 × 1 = 0
  • 3 → 1: distance = 2 → cost = 2 × 2 = 4
  • 2 → 1: distance = 1 → cost = 1 × 1 = 1
  • Total cost = 0 + 4 + 1 = 5

Try making all numbers equal to 3:

  • 1 → 3: distance = 2 → cost = 2 × 1 = 2
  • 3 → 3: distance = 0 → cost = 0 × 2 = 0
  • 2 → 3: distance = 1 → cost = 1 × 1 = 1
  • Total cost = 2 + 0 + 1 = 3

Try making all numbers equal to 2:

  • 1 → 2: distance = 1 → cost = 1 × 1 = 1
  • 3 → 2: distance = 1 → cost = 1 × 2 = 2
  • 2 → 2: distance = 0 → cost = 0 × 1 = 0
  • Total cost = 1 + 2 + 0 = 3

Final Answer:

We tried targets:

  • 1 → cost = 5
  • 3 → cost = 3
  • 2 → cost = 3

So the minimum total cost is 3, and the best target values are either 2 or 3.

Minimum Cost to Make Array Equal Algorithm

Steps:

  1. Initialize the answer:
    • Set a variable ans to a large value (e.g., Long.MAX_VALUE)
  2. Loop through each element in nums[]:
    • Let this element be the target value.
    • For each target, calculate the cost to convert all other elements in nums[] to target.
  3. Calculate total cost for current target:
    • Initialize totalCost = 0.
    • For each index i in nums[]:
      • Compute the absolute difference between nums[i] and target
      • Multiply the difference by cost[i]
      • Add the result to totalCost
  4. Update the answer:
    • Compare totalCost with ans
    • If totalCost is smaller, update ans.
  5. Return the final answer:
    • After trying all possible targets, return ans.

Dry-Run

Input:

  • nums = [1, 3, 2]
  • cost = [1, 2, 1]

Step 1: Initialize answer

  • ans = Long.MAX_VALUE

Step 2: Loop over each number in nums and treat it as the target value.

First target: 1

  • Calculate total cost to make all elements equal to 1:
    • For nums[0] = 1: difference is |1 - 1| = 0, cost is 0 * 1 = 0
    • For nums[1] = 3: difference is |3 - 1| = 2, cost is 2 * 2 = 4
    • For nums[2] = 2: difference is |2 - 1| = 1, cost is 1 * 1 = 1
  • Total cost for target 1 is 0 + 4 + 1 = 5.
  • Update ans to minimum of current ans and 5 → ans = 5.

Second target: 3

  • Calculate total cost to make all elements equal to 3:
    • For nums[0] = 1: difference is |1 - 3| = 2, cost is 2 * 1 = 2
    • For nums[1] = 3: difference is |3 - 3| = 0, cost is 0 * 2 = 0
    • For nums[2] = 2: difference is |2 - 3| = 1, cost is 1 * 1 = 1
  • Total cost for target 3 is 2 + 0 + 1 = 3.
  • Update ans to minimum of current ans and 3 → ans = 3.

Third target: 2

  • Calculate total cost to make all elements equal to 2:
    • For nums[0] = 1: difference is |1 - 2| = 1, cost is 1 * 1 = 1
    • For nums[1] = 3: difference is |3 - 2| = 1, cost is 1 * 2 = 2
    • For nums[2] = 2: difference is |2 - 2| = 0, cost is 0 * 1 = 0
  • Total cost for target 2 is 1 + 2 + 0 = 3.
  • Update ans to minimum of current ans and 3 → ans = 3.

Step 3: Return the minimum cost

  • The minimum total cost to make all elements equal is 3.

Minimum Cost to Make Array Equal Solution

Now let's check out the Minimum Cost to Make Array Equal code in C++ , Java, Python and JavaScript.

"Minimum Cost to Make Array Equal" Code in all Languages.
1. Minimum Cost to Make Array Equal solution in C++ Try on Compiler 
#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
using namespace std;

class Solution {
public:
    // Function to calculate total cost to convert all to tar
    long long getOp(const vector<int>& nums, const vector<int>& cost, int tar) {
        long long op = 0;
        for (int i = 0; i < nums.size(); i++) {
            op += 1LL * abs(tar - nums[i]) * cost[i];
        }
        return op;
    }

    // Brute force: try all nums[i] as target
    long long minCost(const vector<int>& nums, const vector<int>& cost) {
        long long ans = LLONG_MAX;
        for (int tar : nums) {
            long long op = getOp(nums, cost, tar);
            ans = min(ans, op);
        }
        return ans;
    }
};

int main() {
    int n;
    cin >> n; // Input size
    vector<int> nums(n), cost(n);

    // Input nums
    for (int i = 0; i < n; i++) cin >> nums[i];

    // Input cost
    for (int i = 0; i < n; i++) cin >> cost[i];

    Solution sol;
    cout << sol.minCost(nums, cost);
    return 0;
}

2. Minimum Cost to Make Array Equal Solution in Java Try on Compiler 
import java.util.*;

public class Main {
    // Function to compute cost to convert all elements to tar
    public static long getOp(int[] nums, int[] cost, int tar) {
        long op = 0;
        for (int i = 0; i < nums.length; i++) {
            op += 1L * Math.abs(tar - nums[i]) * cost[i];
        }
        return op;
    }

    // Try all nums[i] as possible target
    public long minCost(int[] nums, int[] cost) {
        long ans = Long.MAX_VALUE;
        for (int tar : nums) {
            long op = getOp(nums, cost, tar);
            ans = Math.min(ans, op);
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // Array size

        int[] nums = new int[n];
        int[] cost = new int[n];

        // Read nums array
        for (int i = 0; i < n; i++) nums[i] = sc.nextInt();

        // Read cost array
        for (int i = 0; i < n; i++) cost[i] = sc.nextInt();

        Main sol = new Main();
        System.out.println(sol.minCost(nums, cost));
    }
}

3. Minimum Cost to Make Array Equal Solution in Python Try on Compiler 
def get_op(nums, cost, tar):
    # Calculate cost to convert all elements to tar
    op = 0
    for i in range(len(nums)):
        op += abs(nums[i] - tar) * cost[i]
    return op

def min_cost(nums, cost):
    # Try every element in nums as a possible target
    ans = float('inf')
    for tar in nums:
        op = get_op(nums, cost, tar)
        ans = min(ans, op)
    return ans

if __name__ == "__main__":
    n = int(input())  # Input size
    nums = list(map(int, input().split()))  # nums array
    cost = list(map(int, input().split()))  # cost array
    print(min_cost(nums, cost))

4. Minimum Cost to Make Array Equal solution in JavaScript Try on Compiler 
function getOp(nums, cost, tar) {
    // Calculate cost to convert all elements to tar
    let op = 0;
    for (let i = 0; i < nums.length; i++) {
        op += Math.abs(nums[i] - tar) * cost[i];
    }
    return op;
}

function minCost(nums, cost) {
    // Try every nums[i] as potential target
    let ans = Number.MAX_SAFE_INTEGER;
    for (let tar of nums) {
        let op = getOp(nums, cost, tar);
        ans = Math.min(ans, op);
    }
    return ans;
}

// Node.js main function
const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let input = [];

rl.on("line", function (line) {
    input.push(line.trim());
    if (input.length === 3) {
        const n = parseInt(input[0]);
        const nums = input[1].split(' ').map(Number);
        const cost = input[2].split(' ').map(Number);
        console.log(minCost(nums, cost));
        rl.close();
    }
});

Minimum Cost to Make Array Equal Complexity Analysis

Time Complexity: O(n* n)(TLE)

Let n = size of the input arrays nums and cost.

Breakdown:

  1. Outer Loop (for (int tar : nums)):
    • Runs n times — one for each potential target value in nums.
  3. Inner Operation (getOp function):
    • For each target, you iterate through the full array (nums, cost) → O(n) time.
  5. Total : O(n) * O(n) = O(n^2)

Space Complexity: O(1)

We are not using any extra space apart from:

    • Input arrays nums and cost
    • Primitive variables (op, ans, etc.)

✅ Space Complexity = O(1) (ignoring input arrays)

While the brute-force solution checks every possible target value from the input array, leading to a time complexity of O(n²), how can we optimize the checking instead of blindly checking every option? we can analyze how the total cost changes with different target values and use that pattern to guide our search more efficiently.

Optimal Approach 1 :

Intuition

In our above approach, we are checking for every possible value in array as target. But if we observe as we change the target, the total cost changes in a predictable way — if moving the target one step lowers the cost, it’s worth exploring in that direction; if it increases the cost, you move the other way. This means we don’t have to check every possibility - by comparing costs at different points, we can quickly narrow down where the minimum cost lies.

Now, the question arises that how can we do this?

To avoid checking every value, we need a strategy that helps us decide where to look next. Since the total cost behaves in a consistent way as we adjust the target, we can apply a method that compares costs at carefully chosen points and moves toward the side where the cost is smaller. By repeatedly doing this, we get closer to the value that gives the lowest cost, without wasting time on unnecessary checks. This approach significantly reduces the number of steps and makes the solution much more efficient.

This guided approach helps us avoid checking every value. By comparing nearby target costs and moving in the direction where the cost decreases, we steadily close in on the minimum. Since we’re always narrowing our range based on comparisons, this naturally leads us to apply binary search over the possible target values to find the optimal solution efficiently.

Minimum Cost to Make Array Equal Algorithm

Step 1: Initialize Search Space

  • Set l (left boundary) as the minimum value in nums[].
  • Set r (right boundary) as the maximum value in nums[].
  • We only need to search between the smallest and largest number, as the optimal target value will lie within this range.

Step 2: Binary Search on Target Value

  • While l < r:
    • Calculate the middle point mid = l + (r - l) / 2.
    • Use the getCost() function to compute:
      • cost1 : cost to make all numbers equal to mid.
      • cost2 : cost to make all numbers equal to mid + 1.
    • Update the minimum cost seen so far using ans = min(cost1, cost2).
    • If cost1 < cost2, the minimum lies on the left side → set r = mid.
    • Else, move to the right → set l = mid + 1.

Step 3: Return Final Answer

  • After the loop, return the minimum cost found (ans).

Helper Function: getCost(nums, cost, tar)

  • Initialize total cost as 0.
  • For each element i:
    • Compute |nums[i] - tar| * cost[i].
    • add this into total cost.
  • Return the total cost.

Dry-Run

Input

nums = [1, 3, 2]
cost = [1, 2, 1]

Step 1: Initialize the search range

  • l = 1 (minimum value in nums)
  • r = 3 (maximum value in nums)
  • ans = ∞ (we'll store the minimum cost we find)

Step 2: First iteration of binary search

  • Calculate mid = (1 + 3) / 2 = 2

Now try converting every element in nums to 2:

Cost to convert all to 2:

  • |1 - 2| * 1 = 1
  • |3 - 2| * 2 = 2
  • |2 - 2| * 1 = 0
  • Total = 1 + 2 + 0 = 3 → cost1

Also try converting all to mid + 1 = 3:

Cost to convert all to 3:

  • |1 - 3| * 1 = 2
  • |3 - 3| * 2 = 0
  • |2 - 3| * 1 = 1
  • Total = 2 + 0 + 1 = 3 → cost2

We compare both:

  • cost1 = 3, cost2 = 3
  • Update ans = min(3, 3) = 3

Since cost1 <= cost2, we move left:

  • Update r = mid = 2

Step 3: Second iteration

  • Now, l = 2, r = 2 → loop ends (l is no longer less than r)

Final Answer:

  • The minimum total cost is 3.

Minimum Cost to Make Array Equal Solution

Now let's check out the Minimum Cost to Make Array Equal code in C++ , Java, Python and JavaScript.

"Minimum Cost to Make Array Equal" Code in all Languages.
1. Minimum Cost to Make Array Equal solution in C++ Try on Compiler 
#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
using namespace std;

class Solution {
public:
    // Function to calculate cost for making all elements equal to target
    long long getCost(vector<int>& nums, vector<int>& cost, int tar) {
        long long op = 0;
        for (int i = 0; i < nums.size(); i++) {
            op += 1LL * abs(nums[i] - tar) * cost[i];
        }
        return op;
    }

    // Function to find minimum total cost using binary search
    long long minCost(vector<int>& nums, vector<int>& cost) {
        int l = INT_MAX;
        int r = INT_MIN;

        // Finding the range (min and max in nums)
        for (int i : nums) {
            l = min(l, i);
            r = max(r, i);
        }

        long long ans = LLONG_MAX;

        // Binary search to find the optimal target
        while (l < r) {
            int mid = l + (r - l) / 2;
            long long cost1 = getCost(nums, cost, mid);
            long long cost2 = getCost(nums, cost, mid + 1);
            ans = min(cost1, cost2);

            if (cost1 < cost2) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
};

int main() {
    int n;
    cin >> n; // Length of arrays
    vector<int> nums(n), cost(n);
    
    // Input nums array
    for (int i = 0; i < n; ++i) cin >> nums[i];
    
    // Input cost array
    for (int i = 0; i < n; ++i) cin >> cost[i];
    
    Solution sol;
    cout << sol.minCost(nums, cost);
    return 0;
}

2. Minimum Cost to Make Array Equal Solution in Java Try on Compiler 
import java.util.*;

public class Main {
    // Function to calculate cost for target value
    public static long getCost(int[] nums, int[] cost, int tar) {
        long op = 0;
        for (int i = 0; i < nums.length; i++) {
            op += 1L * Math.abs(tar - nums[i]) * cost[i];
        }
        return op;
    }

    // Function to find minimum total cost
    public long minCost(int[] nums, int[] cost) {
        int l = Integer.MAX_VALUE;
        int r = Integer.MIN_VALUE;

        // Determine min and max in nums
        for (int i : nums) {
            l = Math.min(i, l);
            r = Math.max(i, r);
        }

        long ans = Long.MAX_VALUE;

        // Binary search on value space
        while (l < r) {
            int mid = l + (r - l) / 2;
            long cost1 = getCost(nums, cost, mid);
            long cost2 = getCost(nums, cost, mid + 1);
            ans = Math.min(cost1, cost2);

            if (cost1 < cost2) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // Input size

        int[] nums = new int[n];
        int[] cost = new int[n];

        // Input nums array
        for (int i = 0; i < n; i++) nums[i] = sc.nextInt();

        // Input cost array
        for (int i = 0; i < n; i++) cost[i] = sc.nextInt();

        Main sol = new Main();
        System.out.println(sol.minCost(nums, cost));
    }
}

3. Minimum Cost to Make Array Equal Solution in Python Try on Compiler 
def get_cost(nums, cost, tar):
    # Compute cost for making all elements equal to tar
    op = 0
    for i in range(len(nums)):
        op += abs(tar - nums[i]) * cost[i]
    return op

def min_cost(nums, cost):
    # Determine the min and max in nums
    l = min(nums)
    r = max(nums)
    ans = float('inf')

    # Binary search over value space
    while l < r:
        mid = (l + r) // 2
        cost1 = get_cost(nums, cost, mid)
        cost2 = get_cost(nums, cost, mid + 1)
        ans = min(cost1, cost2)

        if cost1 < cost2:
            r = mid
        else:
            l = mid + 1
    return ans

if __name__ == "__main__":
    n = int(input())                # Input size
    nums = list(map(int, input().split()))  # Input nums array
    cost = list(map(int, input().split()))  # Input cost array
    print(min_cost(nums, cost))

4. Minimum Cost to Make Array Equal solution in JavaScript Try on Compiler 
function getCost(nums, cost, tar) {
    // Calculate cost for converting all to tar
    let op = 0;
    for (let i = 0; i < nums.length; i++) {
        op += Math.abs(tar - nums[i]) * cost[i];
    }
    return op;
}

function minCost(nums, cost) {
    // Find min and max values in nums
    let l = Math.min(...nums);
    let r = Math.max(...nums);
    let ans = Number.MAX_SAFE_INTEGER;

    // Binary search over values
    while (l < r) {
        let mid = Math.floor((l + r) / 2);
        let cost1 = getCost(nums, cost, mid);
        let cost2 = getCost(nums, cost, mid + 1);
        ans = Math.min(cost1, cost2);

        if (cost1 < cost2) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    return ans;
}

// Node.js main function
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let input = [];

rl.on('line', function (line) {
    input.push(line.trim());
    if (input.length === 3) {
        const n = parseInt(input[0]);
        const nums = input[1].split(' ').map(Number);
        const cost = input[2].split(' ').map(Number);
        console.log(minCost(nums, cost));
        rl.close();
    }
});

Minimum Cost to Make Array Equal Complexity Analysis

Time Complexity: O(n log R)

  1. Finding the minimum and maximum in nums
  • We iterate through the array once to find the smallest and largest values.
  • Time taken: O(n)
  1. Binary Search over the range [min, max]
  • The range size is R = max(nums) - min(nums).
  • Binary search runs in O(log R) steps.
  1. Cost calculation inside each binary search step
  • For each candidate target value, we calculate the total cost by looping through all elements.
  • Each calculation takes O(n) time.
  1. Total time complexity
  • Combining binary search steps and cost calculation:

O(log R) × O(n) = O(n log R)

Space Complexity: O(1)

  1. Input storage
  • The input arrays nums and cost are given and don’t count toward extra space used by the algorithm.
  1. Variables used
  • We use a fixed number of variables like l, r, mid, ans, and loop counters.
  • These use constant space, i.e., O(1).
  1. No additional data structures
  • The algorithm does not create any new arrays or data structures proportional to n.
  • All computations happen using the input arrays and a few variables.

Final Space Complexity: O(1) (constant space)

Optimal Approach 2

Intuition

now in the above binary search solution, we are finding the minimum efficiently by reducing the amount of checks we are targeting but initializing the target range between maximum and minimum of array and then applying binary Search on it.

But even with binary search, we still need to compute the cost at each step — and if we compute the full sum every time, it’s still O(n) per step.

So, how can we make each cost calculation faster?
Let’s say we choose a target value equal to nums[i]. Our goal is to calculate the total cost of converting every number in the array to this target, where the cost for each element is weighted by how far it is from the target. If we break this down, we can divide the cost into two parts: the left side, which includes all elements smaller than the target (i.e., nums[0] to nums[i-1]), and the right side, which includes all elements larger than the target (i.e., nums[i+1] to nums[n-1]).

The left-side cost is calculated by summing up the difference between the target and each smaller number, weighted by its individual cost.

Similarly, the right-side cost is calculated by summing up the difference between the target and each greater number, weighted by its individual cost.

Both of these are essentially weighted sums of absolute differences.

Now, if we Notice how similar the calculations are for every target = nums[i] changing? The only thing changing is which elements are to the left and right of the target. That gives us a hint:
what If we precompute the cumulative cost and weighted cost for all prefixes, now we can reuse them.
So here’s what we do:

Sort the array based on nums[i], because we need to know what lies to the left and right of a candidate target. Now we precompute two helper arrays. The first is prefixCost[i], which stores the sum of all cost[j] values from index 0 to i. The second is prefixWeighted[i], which stores the cumulative sum of nums[j] * cost[j] for the same range. These arrays let us quickly access how much total "weight" or cost lies to the left or right of any chosen target value.

Now, suppose we pick nums[i] as our target. We can calculate the cost to move all elements less than nums[i] up to it the left side cost. — using this formula:

LeftCost=nums[i]⋅prefixCost[i−1]−prefixWeighted[i−1]

This works because we’re basically summing the difference between the target and all smaller values, weighted by their cost, and prefix sums let us do that instantly.

Similarly, the cost to bring all values greater than nums[i] down to it — the right side cost

RightCost=(prefixWeighted[n−1]−prefixWeighted[i])−nums[i]⋅ (prefixCost[n−1]−prefixCost[i]).

With these formulas, we can compute the total cost of choosing any nums[i] as the target in constant time. Thanks to the prefix sums we built up front, there's no need to recalculate the entire sum for every possible target. This makes our solution not just faster, but also elegant and scalable.

Minimum Cost to Make Array Equal Algorithm

Step 1: Pair and Sort

Create and sort the input data:

  1. Create a list of pairs:
    (nums[i], cost[i]) for all i
  2. Sort this list based on the values in nums[i]
  3. Extract two sorted arrays:
    • sortedNums[]: values of nums[i] after sorting
    • sortedCost[]: corresponding cost[i] values

Step 2: Build Prefix Arrays

Let n be the length of the input.

Create two prefix arrays:

  • prefixCost[i]: cumulative sum of sortedCost[0...i].
  • prefixWeighted[i]: cumulative sum of sortedNums[i] * sortedCost[i] from 0 to i.

For each i from 0 to n - 1:

  • If i == 0:
    • prefixCost[0] = sortedCost[0]
    • prefixWeighted[0] = sortedNums[0] * sortedCost[0]
  • Else:
    • prefixCost[i] = prefixCost[i - 1] + sortedCost[i]
    • prefixWeighted[i] = prefixWeighted[i - 1] + sortedNums[i] * sortedCost[i]

Step 3: Iterate and Compute Total Cost Efficiently

Initialize minCost = ∞

For each index i from 0 to n - 1 (i.e., consider sortedNums[i] as the target):

1. Compute Left Side Cost (nums[0...i-1] → target)

  • If i == 0:
    LeftCost = 0
  • Else:
    LeftCost = sortedNums[i] * prefixCost[i - 1] - prefixWeighted[i - 1]

2. Compute Right Side Cost (nums[i+1...n-1] → target)

  • If i == n - 1:
    RightCost = 0
  • Else:
    RightCost = (prefixWeighted[n - 1] - prefixWeighted[i]) - sortedNums[i] * (prefixCost[n - 1] - prefixCost[i])

3. Compute Total Cost

  • totalCost = LeftCost + RightCost
  • Update minCost = min(minCost, totalCost)

Step 4: Return Final Answer

  • Return minCost as the minimum total cost to equalize the array.

Dry-Run

Input:

nums = [1, 3, 5]
cost = [1, 2, 1]

Step 1: Pair and Sort

  • Create pairs (nums[i], cost[i]):
    [(1, 1), (3, 2), (5, 1)]
  • Since the array is already sorted by nums, proceed.
  • Extract sorted arrays:
    sortedNums = [1, 3, 5]
    sortedCost = [1, 2, 1]
  • Number of elements, n = 3

Step 2: Build Prefix Arrays

  • Initialize arrays:
    prefixCost = [0, 0, 0]
    prefixWeighted = [0, 0, 0]
  • Calculate prefix sums:
    • For i = 0:
      prefixCost[0] = 1
      prefixWeighted[0] = 1 * 1 = 1
    • For i = 1:
      prefixCost[1] = prefixCost[0] + sortedCost[1] = 1 + 2 = 3
      prefixWeighted[1] = prefixWeighted[0] + sortedNums[1] * sortedCost[1] = 1 + 3*2 = 7
    • For i = 2:
      prefixCost[2] = prefixCost[1] + sortedCost[2] = 3 + 1 = 4
      prefixWeighted[2] = prefixWeighted[1] + sortedNums[2] *sortedCost[2] = 7 + 5*1 = 12

Step 3: Iterate and Compute Total Cost for Each Target

  • Initialize minCost = ∞
  • For each index i from 0 to 2 (target = sortedNums[i]):
    • i = 0 :
    • LeftCost = 0 (no elements to the left)
    • RightCost = (12 - 1) - 1 * (4 - 1) = 11 - 3 = 8
    • TotalCost = 0 + 8 = 8
    • i = 1 :
    • LeftCost = 3 * 1 - 1 = 2
    • RightCost = (12 - 7) - 3 * (4 - 3) = 5 - 3 = 2
    • TotalCost = 2 + 2 = 4
    • Update minCost = 4
    • i = 2 :
    • LeftCost = 5 * 3 - 7 = 15 - 7 = 8
    • RightCost = 0 (no elements to the right)
    • TotalCost = 8 + 0 = 8

Step 4: Return Final Answer

  • The minimum total cost is 4 , achieved when the target value is 3.

Minimum Cost to Make Array Equal Solution

Now let's check out the Minimum Cost to Make Array Equal code in C++ , Java, Python and JavaScript.

"Minimum Cost to Make Array Equal" Code in all Languages.
1. Minimum Cost to Make Array Equal solution in C++ Try on Compiler 
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

long long minCostToEqualTarget(vector<int>& nums, vector<int>& cost) {
    int n = nums.size();

    // Pairing nums and cost, and sorting by nums
    vector<pair<int,int>> arr(n);
    for (int i = 0; i < n; i++) {
        arr[i] = {nums[i], cost[i]};
    }
    sort(arr.begin(), arr.end());

    // Prefix sums for cost and weighted sum (nums[i] * cost[i])
    vector<long long> prefixCost(n, 0), prefixWeighted(n, 0);
    prefixCost[0] = arr[0].second;
    prefixWeighted[0] = (long long)arr[0].first * arr[0].second;

    for (int i = 1; i < n; i++) {
        prefixCost[i] = prefixCost[i-1] + arr[i].second;
        prefixWeighted[i] = prefixWeighted[i-1] + (long long)arr[i].first * arr[i].second;
    }

    long long minCost = LLONG_MAX;

    // Try each element as the target
    for (int i = 0; i < n; i++) {
        long long leftCost = 0, rightCost = 0;
        int target = arr[i].first;

        // Calculate left cost (elements smaller than target)
        if (i > 0) {
            leftCost = (long long)target * prefixCost[i-1] - prefixWeighted[i-1];
        }

        // Calculate right cost (elements greater than target)
        if (i < n - 1) {
            rightCost = (prefixWeighted[n-1] - prefixWeighted[i]) - (long long)target * (prefixCost[n-1] - prefixCost[i]);
        }

        // Combine both sides
        long long totalCost = leftCost + rightCost;
        minCost = min(minCost, totalCost);
    }

    return minCost;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n), cost(n);

    // Input nums
    for (int i = 0; i < n; i++) cin >> nums[i];

    // Input cost
    for (int i = 0; i < n; i++) cin >> cost[i];

    // Output minimum cost
    cout << minCostToEqualTarget(nums, cost) << "\n";

    return 0;
}

2. Minimum Cost to Make Array Equal Solution in Java Try on Compiler 
import java.util.*;

public class Main {

    public static long minCostToEqualTarget(int[] nums, int[] cost) {
        int n = nums.length;
        int[][] arr = new int[n][2];

        // Pair nums with cost
        for (int i = 0; i < n; i++) {
            arr[i][0] = nums[i];
            arr[i][1] = cost[i];
        }

        // Sort by nums
        Arrays.sort(arr, Comparator.comparingInt(a -> a[0]));

        // Prefix sum arrays
        long[] prefixCost = new long[n];
        long[] prefixWeighted = new long[n];

        prefixCost[0] = arr[0][1];
        prefixWeighted[0] = (long) arr[0][0] * arr[0][1];

        // Compute prefix sums
        for (int i = 1; i < n; i++) {
            prefixCost[i] = prefixCost[i - 1] + arr[i][1];
            prefixWeighted[i] = prefixWeighted[i - 1] + (long) arr[i][0] * arr[i][1];
        }

        long minCost = Long.MAX_VALUE;

        // Try each as target
        for (int i = 0; i < n; i++) {
            int target = arr[i][0];
            long leftCost = 0, rightCost = 0;

            // Left cost
            if (i > 0) {
                leftCost = (long) target * prefixCost[i - 1] - prefixWeighted[i - 1];
            }

            // Right cost
            if (i < n - 1) {
                rightCost = (prefixWeighted[n - 1] - prefixWeighted[i]) - (long) target * (prefixCost[n - 1] - prefixCost[i]);
            }

            // Total cost
            long totalCost = leftCost + rightCost;
            minCost = Math.min(minCost, totalCost);
        }

        return minCost;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] nums = new int[n];
        int[] cost = new int[n];

        // Input nums
        for (int i = 0; i < n; i++) nums[i] = sc.nextInt();

        // Input cost
        for (int i = 0; i < n; i++) cost[i] = sc.nextInt();

        // Output result
        System.out.println(minCostToEqualTarget(nums, cost));
        sc.close();
    }
}

3. Minimum Cost to Make Array Equal Solution in Python Try on Compiler 
def min_cost_to_equal_target(nums, cost):
    n = len(nums)

    # Pair and sort by nums
    arr = sorted(zip(nums, cost), key=lambda x: x[0])

    # Prefix sums
    prefix_cost = [0] * n
    prefix_weighted = [0] * n

    prefix_cost[0] = arr[0][1]
    prefix_weighted[0] = arr[0][0] * arr[0][1]

    for i in range(1, n):
        prefix_cost[i] = prefix_cost[i - 1] + arr[i][1]
        prefix_weighted[i] = prefix_weighted[i - 1] + arr[i][0] * arr[i][1]

    min_cost = float('inf')

    # Try each as target
    for i in range(n):
        target = arr[i][0]

        # Left cost
        left_cost = target * prefix_cost[i - 1] - prefix_weighted[i - 1] if i > 0 else 0

        # Right cost
        right_cost = (prefix_weighted[n - 1] - prefix_weighted[i]) - target * (prefix_cost[n - 1] - prefix_cost[i]) if i < n - 1 else 0

        # Total cost
        total_cost = left_cost + right_cost
        min_cost = min(min_cost, total_cost)

    return min_cost


if __name__ == "__main__":
    n = int(input())
    nums = list(map(int, input().split()))
    cost = list(map(int, input().split()))

    # Output result
    print(min_cost_to_equal_target(nums, cost))

4. Minimum Cost to Make Array Equal solution in JavaScript Try on Compiler 
process.stdin.resume();
process.stdin.setEncoding('utf8');

let inputData = '';
process.stdin.on('data', function(chunk) {
    inputData += chunk;
});

process.stdin.on('end', function() {
    const input = inputData.trim().split(/\s+/);
    const n = parseInt(input[0]);
    const nums = input.slice(1, n + 1).map(Number);
    const cost = input.slice(n + 1).map(Number);

    console.log(minCostToEqualTarget(nums, cost));
});

function minCostToEqualTarget(nums, cost) {
    const n = nums.length;

    // Pair and sort
    let arr = [];
    for (let i = 0; i < n; i++) {
        arr.push([nums[i], cost[i]]);
    }
    arr.sort((a, b) => a[0] - b[0]);

    // Prefix sums
    let prefixCost = Array(n).fill(0);
    let prefixWeighted = Array(n).fill(0);

    prefixCost[0] = arr[0][1];
    prefixWeighted[0] = arr[0][0] * arr[0][1];

    for (let i = 1; i < n; i++) {
        prefixCost[i] = prefixCost[i - 1] + arr[i][1];
        prefixWeighted[i] = prefixWeighted[i - 1] + arr[i][0] * arr[i][1];
    }

    let minCost = Number.MAX_SAFE_INTEGER;

    // Try each as target
    for (let i = 0; i < n; i++) {
        const target = arr[i][0];

        // Left and right costs
        let leftCost = i > 0 ? target * prefixCost[i - 1] - prefixWeighted[i - 1] : 0;
        let rightCost = i < n - 1 ? (prefixWeighted[n - 1] - prefixWeighted[i]) - target * (prefixCost[n - 1] - prefixCost[i]) : 0;

        const totalCost = leftCost + rightCost;
        minCost = Math.min(minCost, totalCost);
    }

    return minCost;
}

Minimum Cost to Make Array Equal Complexity Analysis

Time Complexity: O(n* logn)

Let’s break it down step by step:

  • Pairing and Sorting:
    • We first pair nums[i] with cost[i] and sort them based on nums[i].
    • Sorting takes O(n log n) time where n is the number of elements.
    • Pairing takes O(n), but sorting dominates this step.
  • Prefix Sum Computation:
    • We compute two prefix arrays: prefixCost and prefixWeighted.
    • This is a single pass through the array, so it takes O(n) time.
  • Cost Calculation Loop:
    • For each element, we try it as the target and compute the total cost using prefix arrays.
    • Each cost computation takes O(1) time due to prefix sums.
    • There are n iterations, so this step takes O(n) time.
  • Total Time Complexity:
    • Sorting: O(n log n)
    • Prefix computation: O(n)
    • Cost checking loop: O(n)
    • Final: O(n log n)

Space Complexity: O(n)

Here’s where the memory is used:

  • Paired Array (nums[i], cost[i]):
    • We create a new array of size n to store pairs.
    • This uses O(n) space.
  • Prefix Arrays:
    • prefixCost[n] and prefixWeighted[n] store cumulative values.
    • Each is size n, so together they use O(n) space.
  • Other Variables:
    • We use a few integers and long variables, but those are constant and don't grow with input size.
    • So, they contribute O(1) to space complexity.
  • Final: O(n)

Similar Problems

Minimum Moves to Equal Array Elements II

Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.

In one move, you can increment or decrement an element of the array by 1.

Test cases are designed so that the answer will fit in a 32-bit integer.

Maximum Product of the Length of Two Palindromic Substrings

You are given a 0-indexed string s and are tasked with finding two non-intersecting palindromic substrings of odd length such that the product of their lengths is maximized.

More formally, you want to choose four integers i, j, k, l such that 0 <= i <= j < k <= l < s.length and both the substrings s[i...j] and s[k...l] are palindromes and have odd lengths. s[i...j] denotes a substring from index i to index j inclusive.

Return the maximum possible product of the lengths of the two non-intersecting palindromic substrings.

A palindrome is a string that is the same forward and backward. A substring is a contiguous sequence of characters in a string.

Minimum Amount of Time to Fill Cups

You have a water dispenser that can dispense cold, warm, and hot water. Every second, you can either fill up 2 cups with different types of water, or 1 cup of any type of water.

You are given a 0-indexed integer array amount of length 3 where amount[0], amount[1], and amount[2] denote the number of cold, warm, and hot water cups you need to fill respectively. Return the minimum number of seconds needed to fill up all the cups.

Minimum Operations to Make All Array Elements Equal

You are given an array nums consisting of positive integers.

You are also given an integer array queries of size m. For the ith query, you want to make all of the elements of nums equal to queries[i]. You can perform the following operation on the array any number of times:

  • Increase or decrease an element of the array by 1.

Return an array answer of size m where answer[i] is the minimum number of operations to make all elements of nums equal to queries[i].

Note that after each query the array is reset to its original state.

Minimum Cost to Make Array Equalindromic

You are given a 0-indexed integer array nums having length n.

You are allowed to perform a special move any number of times (including zero) on nums. In one special move you perform the following steps in order:

  • Choose an index i in the range [0, n - 1], and a positive integer x.
  • Add |nums[i] - x| to the total cost.
  • Change the value of nums[i] to x.

A palindromic number is a positive integer that remains the same when its digits are reversed. For example, 121, 2552 and 65756 are palindromic numbers whereas 24, 46, 235 are not palindromic numbers.

An array is considered equalindromic if all the elements in the array are equal to an integer y, where y is a palindromic number less than 109.

Return an integer denoting the minimum possible total cost to make nums equalindromic by performing any number of special moves.