LeetCode 2448 - Minimum Cost to Make Array Equal

LeetCode Problem 2448

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Greedy, Sorting, Prefix Sum

Solution

This guide will use the weighted median optimization approach, which is the key insight behind solving this problem efficiently within the constraints.

Problem Understanding

The problem gives us two arrays, nums and cost, each of length n.

The nums[i] value represents the current number at index i, and cost[i] represents how expensive it is to change that number by 1. We may repeatedly increase or decrease any number by one unit, paying cost[i] for every unit change.

Our goal is to make all elements in nums equal, while minimizing the total accumulated cost.

In other words, we want to choose some target value x and transform every number into x. The cost for index i becomes:

$$|nums[i] - x| \times cost[i]$$

The total cost for a chosen target x is:

$$\sum |nums[i] - x| \times cost[i]$$

We must return the minimum possible total cost.

The constraints are important:

• n can be as large as 10^5
• nums[i] and cost[i] can be as large as 10^6

A naive approach that tries every possible target value and computes the cost directly would be far too slow. Since values can be up to one million and the array size can be very large, we need an algorithm that scales efficiently.

The problem guarantees:

• All numbers are positive integers
• nums and cost have equal lengths
• The answer fits within 2^53 - 1, which matters especially for languages with fixed-size integer types

Several edge cases are important upfront.

If all numbers are already equal, the answer should be 0, since no operations are necessary.

When one element has an extremely large cost compared to others, the optimal target often becomes that number's value because moving it would be too expensive.

Duplicate values can also matter because multiple elements may already align with a strong weighted center.

A naive implementation may also overflow if integer arithmetic is not handled carefully, particularly in Go, where we must use int64.

Approaches

Brute Force Approach

The most direct approach is to try every possible target value and calculate the total cost of converting all numbers into that target.

For each possible target x, we compute:

$$\sum |nums[i] - x| \times cost[i]$$

Then we return the minimum cost among all candidates.

Because nums[i] can be as large as 10^6, we might try every integer between the minimum and maximum value in nums.

This works because the optimal answer must correspond to some integer target. By exhaustively evaluating every possibility, we guarantee correctness.

However, this approach is too slow.

If the value range is about 10^6, and for each candidate we scan n = 10^5 elements, the total complexity becomes:

$$O(n \times range)$$

which is too expensive.

Key Insight for the Optimal Approach

The total cost function is:

$$f(x) = \sum |nums[i] - x| \times cost[i]$$

This is a weighted absolute distance minimization problem.

For regular absolute distances, the median minimizes:

$$\sum |a_i - x|$$

When every point has a weight, the minimizing point becomes the weighted median.

A weighted median is the value where the cumulative weight reaches at least half of the total weight.

Why does this work?

Imagine moving the target value left or right.

If too much weighted mass exists on one side, moving toward that side reduces the total weighted distance. At equilibrium, neither direction improves the answer. That balancing point is precisely the weighted median.

So instead of checking every target value, we:

1. Pair each number with its cost.
2. Sort by number.
3. Find the weighted median.
4. Compute the total cost to convert everything into that median.

This produces the optimal answer efficiently.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × range)	O(1)	Try every possible target value
Optimal	O(n log n)	O(n)	Sort and use weighted median

Algorithm Walkthrough

Optimal Algorithm Using Weighted Median

1. Combine nums and cost into pairs.

We want each number to remain associated with its corresponding modification cost, so we create pairs like:

(nums[i], cost[i]) 2. Sort the pairs by number.

Since the weighted median depends on ordering, we sort by the values in nums. 3. Compute the total weight.

Add all values in cost:

$$totalWeight = \sum cost[i]$$ 4. Find the weighted median.

Traverse the sorted pairs while accumulating costs.

Once cumulative weight becomes at least:

$$\frac{totalWeight + 1}{2}$$

we stop.

The corresponding number becomes the weighted median. 5. Compute the final minimum cost.

For every number:

$$|nums[i] - median| \times cost[i]$$

Sum all these values. 6. Return the total.

This is guaranteed to be the minimum possible cost.

Why it works

The objective function is convex because it is the sum of weighted absolute value terms. Moving left or right changes the total cost based on how much weight exists on each side. The weighted median is exactly the balancing point where shifting in either direction cannot reduce the total weighted distance. Therefore, choosing the weighted median guarantees the minimum total cost.

Python Solution

from typing import List

class Solution:
    def minCost(self, nums: List[int], cost: List[int]) -> int:
        pairs = sorted(zip(nums, cost))

        total_cost_weight = sum(cost)
        half_weight = (total_cost_weight + 1) // 2

        current_weight = 0
        target = 0

        for num, c in pairs:
            current_weight += c
            if current_weight >= half_weight:
                target = num
                break

        minimum_cost = 0

        for num, c in zip(nums, cost):
            minimum_cost += abs(num - target) * c

        return minimum_cost

Implementation Walkthrough

The implementation begins by pairing each number with its corresponding cost using zip(nums, cost). We immediately sort these pairs because finding the weighted median requires processing numbers in sorted order.

Next, we calculate the total weight by summing all values in cost. Since the weighted median is the point where cumulative weight crosses half of the total, we compute:

half_weight = (total_cost_weight + 1) // 2

This ensures correct handling when the total weight is odd.

We then scan the sorted pairs while maintaining a running cumulative weight. As soon as the cumulative sum reaches at least half the total weight, we stop. That number becomes the optimal target.

Finally, we compute the total transformation cost by summing:

abs(num - target) * cost

for every element. This directly models the cost definition in the problem statement.

Go Solution

package main

import "sort"

func minCost(nums []int, cost []int) int64 {
	type pair struct {
		num  int
		cost int
	}

	n := len(nums)
	pairs := make([]pair, n)

	for i := 0; i < n; i++ {
		pairs[i] = pair{
			num:  nums[i],
			cost: cost[i],
		}
	}

	sort.Slice(pairs, func(i, j int) bool {
		return pairs[i].num < pairs[j].num
	})

	var totalWeight int64

	for _, c := range cost {
		totalWeight += int64(c)
	}

	halfWeight := (totalWeight + 1) / 2

	var currentWeight int64
	target := 0

	for _, p := range pairs {
		currentWeight += int64(p.cost)

		if currentWeight >= halfWeight {
			target = p.num
			break
		}
	}

	var minimumCost int64

	for i := 0; i < n; i++ {
		diff := nums[i] - target
		if diff < 0 {
			diff = -diff
		}

		minimumCost += int64(diff) * int64(cost[i])
	}

	return minimumCost
}

Go-specific implementation differences

The Go implementation uses a custom pair struct to keep numbers associated with their costs during sorting.

Unlike Python, Go integers may overflow depending on platform size, so we explicitly use int64 for cumulative weights and the final cost computation. This prevents overflow when multiplying large distances by large costs.

Go also does not provide a built-in absolute value function for integers, so we manually handle negative differences.

No special handling for nil versus empty slices is necessary because the problem guarantees valid input lengths.

Worked Examples

Example 1

Input

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

Step 1: Pair and Sort

Number	Cost
1	2
2	14
3	3
5	1

Step 2: Compute Total Weight

$$2 + 14 + 3 + 1 = 20$$

Half weight:

$$(20 + 1) / 2 = 10$$

Step 3: Find Weighted Median

Number	Cost	Running Weight
1	2	2
2	14	16

The cumulative weight first exceeds 10 at value 2.

So:

target = 2

Step 4: Compute Cost

Number	Target	Distance	Cost Multiplier	Total
1	2	1	2	2
3	2	1	3	3
5	2	3	1	3
2	2	0	14	0

Final answer:

2 + 3 + 3 + 0 = 8

Output:

8

Example 2

Input

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

Step 1: Sort

All numbers are already 2.

Step 2: Weighted Median

The weighted median is 2.

Step 3: Compute Cost

Every element already equals the target.

Total cost:

0

Output:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(n)	We store paired values for sorting

The sorting step requires O(n log n) time, which dominates the overall complexity. The weighted median scan and final cost computation are both linear.

The auxiliary space complexity is O(n) because we create a separate array of paired values.

Test Cases

sol = Solution()

assert sol.minCost([1, 3, 5, 2], [2, 3, 1, 14]) == 8  # Example 1
assert sol.minCost([2, 2, 2, 2, 2], [4, 2, 8, 1, 3]) == 0  # Example 2

assert sol.minCost([5], [10]) == 0  # Single element

assert sol.minCost([1, 10], [1, 100]) == 9  # Expensive element dominates

assert sol.minCost([1, 2, 3], [1, 1, 1]) == 2  # Standard median

assert sol.minCost([1, 1000000], [1000000, 1]) == 999999  # Large imbalance

assert sol.minCost([1, 1, 1, 10], [1, 1, 1, 1]) == 9  # Duplicate values

assert sol.minCost([1, 2, 10], [10, 1, 1]) == 9  # Weighted median near heavy cost

assert sol.minCost([1000000, 1000000], [1000000, 1000000]) == 0  # Large equal values

Test	Why
[1,3,5,2]	Verifies provided example
[2,2,2,2,2]	Confirms zero cost when already equal
Single element	Smallest valid input
[1,10] with heavy weight	Ensures weighted median dominates
Equal costs	Behaves like normal median
Extreme values	Validates large distances
Duplicate values	Ensures repeated numbers handled correctly
Heavy left-side weight	Tests weighted balancing
Large equal values	Stress test for integer arithmetic

Edge Cases

All Elements Are Already Equal

When every number in nums is identical, the answer should immediately be 0. This can be a source of bugs if an implementation unnecessarily modifies values or incorrectly computes costs. In our implementation, the weighted median equals the shared value, so every absolute difference becomes zero automatically.

One Element Has an Extremely Large Cost

Consider:

nums = [1, 100]
cost = [1000, 1]

A naive intuition might choose the midpoint, but moving the first element is extremely expensive. The weighted median naturally favors the heavily weighted position, producing the optimal result. Since cumulative cost determines the target, the algorithm correctly selects 1.

Very Large Numbers and Costs

Because both nums[i] and cost[i] may be as large as 10^6, intermediate multiplication can become very large. This is especially dangerous in Go. The implementation prevents overflow by using int64 for cumulative sums and cost calculations.

Multiple Valid Medians

In some cases, several target values may produce the same minimum cost. This happens when the weighted median lies within a range. The algorithm simply selects the first valid weighted median encountered during traversal. Since all values in that interval are optimal, the result remains correct.