Minimum Cost to Make Array Equal - Practice Coding Problems

Minimum Cost to Make Array Equal - Problem

Array Binary Search Greedy Sorting Prefix Sum Hard

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 i^th element is cost[i].

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

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,3,5], cost = [2,3,1]

› Output: 6

💡 Note: Change nums to [3,3,3]: cost = |1-3|×2 + |3-3|×3 + |5-3|×1 = 2×2 + 0×3 + 2×1 = 6

Example 2 — Equal Elements

$ Input: nums = [2,2,2,2], cost = [4,2,8,1]

› Output: 0

💡 Note: All elements are already equal, so no operations needed. Total cost = 0

Example 3 — Large Range

$ Input: nums = [1,10,20], cost = [1,1,1]

› Output: 18

💡 Note: Optimal target is 10: cost = |1-10|×1 + |10-10|×1 + |20-10|×1 = 9 + 0 + 9 = 18

Constraints

n == nums.length
n == cost.length
1 ≤ n ≤ 10⁵
1 ≤ nums[i], cost[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

nums = [1,3,5] with costs = [2,3,1]

Find Target

Optimal target is weighted median = 3

Calculate Cost

Total cost = |1-3|×2 + |3-3|×3 + |5-3|×1 = 6

Key Takeaway

🎯 Key Insight: The optimal target is the weighted median, minimizing total movement cost

Asked in

G Google 12 A Amazon 8 M Microsoft 6

The key insight is that the optimal target value is the weighted median of the array. The weighted median approach gives us O(n log n) time by sorting elements and finding the median point. Binary search can also work efficiently by searching the answer space. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Weighted Median Approach	O(n log n)	O(n)	Find weighted median as optimal target in O(n log n) time
Binary Search on Answer Space	O(n log k)	O(1)	Binary search on possible target values using cost function
Brute Force - Try All Targets	O(k × n)	O(1)	Try every possible target value and calculate total cost

Weighted Median Approach — Algorithm Steps

Create pairs of (value, cost) and sort by value
Calculate total weight sum
Find weighted median where cumulative weight >= total_weight/2
Calculate final cost using the median

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort & Weight

Sort values with their costs as weights

Find Median

Locate weighted median point

Calculate Cost

Compute final cost using optimal target

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int value;
    int cost;
} Pair;

int compare(const void* a, const void* b) {
    return ((Pair*)a)->value - ((Pair*)b)->value;
}

long long solution(int* nums, int* cost, int n) {
    Pair pairs[1000];
    
    // Create pairs and sort by value
    for (int i = 0; i < n; i++) {
        pairs[i].value = nums[i];
        pairs[i].cost = cost[i];
    }
    qsort(pairs, n, sizeof(Pair), compare);
    
    // Find weighted median
    long long totalWeight = 0;
    for (int i = 0; i < n; i++) {
        totalWeight += cost[i];
    }
    
    long long cumulativeWeight = 0;
    int target = 0;
    
    for (int i = 0; i < n; i++) {
        cumulativeWeight += pairs[i].cost;
        if (cumulativeWeight >= totalWeight / 2 + 1) {
            target = pairs[i].value;
            break;
        }
    }
    
    // Calculate total cost
    long long totalCost = 0;
    for (int i = 0; i < n; i++) {
        int diff = nums[i] - target;
        if (diff < 0) diff = -diff;
        totalCost += (long long)diff * cost[i];
    }
    
    return totalCost;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000], cost[1000], n = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    int m = 0;
    token = strtok(line + 1, ",]");
    while (token) {
        cost[m++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%lld\n", solution(nums, cost, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), finding median and calculating cost takes O(n)

⚡ Linearithmic

Space Complexity

O(n)

Need extra space to store sorted pairs of (value, cost)

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Weighted Median Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler