Minimum Cost to Make Array Equal

Hard
1385.

Minimum Cost to Make Array Equal

Minimum Cost to Make Array Equal is a hard coding problem on arrays, sorting and greedy, asked in Amazon, Google and Microsoft interviews.

You are given two arrays of length n: nums and cost. One operation increases or decreases a single element nums[i] by 1 and costs cost[i].

Return the minimum total cost to make every element of nums equal.

CodeKairo bounds: the original allows values and costs up to 10^6 with n up to 10^5, which needs a 64-bit answer. Here n <= 10^4, nums[i] <= 10^4 and cost[i] <= 10, so the answer fits in a 32-bit integer.

Example 1

Input
nums = [1,3,5,2], cost = [2,3,1,14]
Output
8
Explanation
Make every element 2: 1·2 + 1·3 + 3·1 + 0·14 = 8.

Example 2

Input
nums = [2,2,2,2,2], cost = [4,2,8,1,3]
Output
0

Example 3

Input
nums = [10,1], cost = [1,5]
Output
9
Explanation
Moving the cheap element all the way costs 9; any other meeting point costs more.

Constraints

  • n == nums.length == cost.length
  • 1 <= n <= 10^4
  • 1 <= nums[i] <= 10^4
  • 1 <= cost[i] <= 10
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number[]} cost
 * @return {number}
 */
var minCost = function(nums, cost) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Cost to Make Array Equal — Problem & Solution

Minimum Cost to Make Array Equal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimum Cost to Make Array Equal is a hard coding problem on arrays, sorting and greedy, asked in Amazon, Google and Microsoft interviews.

Problem statement

You are given two arrays of length n: nums and cost. One operation increases or decreases a single element nums[i] by 1 and costs cost[i].

Return the minimum total cost to make every element of nums equal.

CodeKairo bounds: the original allows values and costs up to 10^6 with n up to 10^5, which needs a 64-bit answer. Here n <= 10^4, nums[i] <= 10^4 and cost[i] <= 10, so the answer fits in a 32-bit integer.

Example 1

Input: nums = [1,3,5,2], cost = [2,3,1,14]
Output: 8
Explanation: Make every element 2: 1·2 + 1·3 + 3·1 + 0·14 = 8.

Example 2

Input: nums = [2,2,2,2,2], cost = [4,2,8,1,3]
Output: 0

Example 3

Input: nums = [10,1], cost = [1,5]
Output: 9
Explanation: Moving the cheap element all the way costs 9; any other meeting point costs more.

Constraints

  • n == nums.length == cost.length
  • 1 <= n <= 10^4
  • 1 <= nums[i] <= 10^4
  • 1 <= cost[i] <= 10

Hints for Minimum Cost to Make Array Equal

  1. Hint 1

    Write the cost of making everything equal to x as a function f(x) = Σ |nums[i] - x| · cost[i].

  2. Hint 2

    Each term is a V shape, so f is convex: it decreases, then (maybe after a flat stretch) increases.

  3. Hint 3

    Binary-search x between min(nums) and max(nums) by comparing f(mid) with f(mid + 1).

How to solve Minimum Cost to Make Array Equal

The total cost as a function of the common target x is a sum of weighted absolute values, which is convex. The minimum of a convex function over integers can be binary-searched by looking at the sign of its slope f(mid + 1) - f(mid).

Approach

  1. Let lo = min(nums), hi = max(nums) — moving outside that range only adds cost.
  2. While lo < hi: take mid = lo + (hi - lo) / 2; if f(mid) <= f(mid + 1) the minimum is at mid or to its left (hi = mid), otherwise it is to the right (lo = mid + 1).
  3. Return f(lo), computing f with 64-bit accumulation.

Why it works

Each |nums[i] - x| · cost[i] is convex in x, and sums of convex functions are convex, so the slope f(x + 1) - f(x) is non-decreasing. Where it is still negative the minimum lies further right; once it is zero or positive, nothing to the right can be lower than f(mid). That is exactly the invariant the search keeps. (Equivalently, the optimum is the cost-weighted median of nums.)

Complexity

  • Time — O(n log V) with V the value range
  • Space — O(1)

Pitfalls

  • Evaluate f in 64-bit — at a bad x the sum can exceed what the answer needs.
  • Compare f(mid) with f(mid + 1), not with f(mid - 1), to keep mid + 1 inside the range.
  • A target outside [min, max] is never better, so the search range is safe.

Reference solution

Python

from typing import List

def minCost(nums: List[int], cost: List[int]) -> int:
    def f(x):
        return sum(abs(a - x) * c for a, c in zip(nums, cost))
    lo, hi = min(nums), max(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if f(mid) <= f(mid + 1):
            hi = mid
        else:
            lo = mid + 1
    return f(lo)

Java

public static int minCost(int[] nums, int[] cost) {
    int lo = Integer.MAX_VALUE, hi = Integer.MIN_VALUE;
    for (int v : nums) { lo = Math.min(lo, v); hi = Math.max(hi, v); }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (costAt(nums, cost, mid) <= costAt(nums, cost, mid + 1)) hi = mid; else lo = mid + 1;
    }
    return (int) costAt(nums, cost, lo);
}

static long costAt(int[] nums, int[] cost, int x) {
    long s = 0;
    for (int i = 0; i < nums.length; i++) s += (long) Math.abs(nums[i] - x) * cost[i];
    return s;
}

C++

long long costAt(const vector<int>& nums, const vector<int>& cost, int x) {
    long long s = 0;
    for (size_t i = 0; i < nums.size(); i++) s += (long long)abs(nums[i] - x) * cost[i];
    return s;
}

int minCost(vector<int>& nums, vector<int>& cost) {
    int lo = *min_element(nums.begin(), nums.end());
    int hi = *max_element(nums.begin(), nums.end());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (costAt(nums, cost, mid) <= costAt(nums, cost, mid + 1)) hi = mid; else lo = mid + 1;
    }
    return (int)costAt(nums, cost, lo);
}

JavaScript

var minCost = function(nums, cost) {
    var f = function(x) {
        var s = 0;
        for (var i = 0; i < nums.length; i++) s += Math.abs(nums[i] - x) * cost[i];
        return s;
    };
    var lo = Infinity, hi = -Infinity;
    for (var j = 0; j < nums.length; j++) {
        if (nums[j] < lo) lo = nums[j];
        if (nums[j] > hi) hi = nums[j];
    }
    while (lo < hi) {
        var mid = lo + ((hi - lo) >> 1);
        if (f(mid) <= f(mid + 1)) hi = mid; else lo = mid + 1;
    }
    return f(lo);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms