Minimum Operations to Make All Array Elements Equal

Medium
1386.

Minimum Operations to Make All Array Elements Equal

Minimum Operations to Make All Array Elements Equal is a medium coding problem on arrays, sorting and binary search, asked in Amazon and Google interviews.

You are given an array nums and an array queries. One operation adds 1 to or subtracts 1 from a single element of nums.

For each queries[i], find the minimum number of operations that makes every element of nums equal to queries[i]. Each query starts again from the original nums.

Return the answers in query order.

CodeKairo bounds: the original allows values up to 10^9, which needs 64-bit answers. Here values are at most 10^4, so each answer fits in a 32-bit integer.

Example 1

Input
nums = [4,1,7], queries = [4,1,10]
Output
[6,9,18]
Explanation
For 4: 0 + 3 + 3. For 1: 3 + 0 + 6. For 10: 6 + 9 + 3.

Example 2

Input
nums = [2,9,6,3], queries = [10]
Output
[20]

Constraints

  • n == nums.length
  • m == queries.length
  • 1 <= n, m <= 10^5
  • 1 <= nums[i], queries[i] <= 10^4
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[]} queries
 * @return {number[]}
 */
var minOperations = function(nums, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Operations to Make All Array Elements Equal Solution

Minimum Operations to Make All Array Elements Equal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Operations to Make All Array Elements Equal is a medium coding problem on arrays, sorting and binary search, asked in Amazon and Google interviews.

Problem statement

You are given an array nums and an array queries. One operation adds 1 to or subtracts 1 from a single element of nums.

For each queries[i], find the minimum number of operations that makes every element of nums equal to queries[i]. Each query starts again from the original nums.

Return the answers in query order.

CodeKairo bounds: the original allows values up to 10^9, which needs 64-bit answers. Here values are at most 10^4, so each answer fits in a 32-bit integer.

Example 1

Input: nums = [4,1,7], queries = [4,1,10]
Output: [6,9,18]
Explanation: For 4: 0 + 3 + 3. For 1: 3 + 0 + 6. For 10: 6 + 9 + 3.

Example 2

Input: nums = [2,9,6,3], queries = [10]
Output: [20]

Constraints

  • n == nums.length
  • m == queries.length
  • 1 <= n, m <= 10^5
  • 1 <= nums[i], queries[i] <= 10^4

Hints for Minimum Operations to Make All Array Elements Equal

  1. Hint 1

    The answer for target q is Σ |nums[i] - q| — the order of nums does not matter, so sort it.

  2. Hint 2

    In sorted order the elements below q form a prefix and the rest a suffix; their contributions are q · count - sum and sum - q · count.

  3. Hint 3

    Binary-search the split point and read both sums from a prefix-sum array.

How to solve Minimum Operations to Make All Array Elements Equal

Sort once and build prefix sums; then every query is one binary search plus O(1) arithmetic, because the elements below the target and those at or above it each contribute a closed-form total.

Approach

  1. Sort nums and build pre[i] = sum of the first i sorted values.
  2. For a query q, let j be the number of elements smaller than q (lower bound of q).
  3. Raising the small ones costs q · j - pre[j]; lowering the rest costs (pre[n] - pre[j]) - q · (n - j).
  4. The answer is the sum of the two parts.

Why it works

|v - q| equals q - v for v < q and v - q otherwise, so summing over the two groups separately removes the absolute value. Sorting makes the first group a prefix, whose size is the lower bound of q and whose sum is a prefix sum.

Complexity

  • Time — O((n + m) log n)
  • Space — O(n)

Pitfalls

  • Each query is independent — do not carry changes from one query to the next.
  • Elements equal to q cost nothing on either side; the split can put them in either group.
  • With the original 10^9 bounds the sums need 64-bit integers; keep the habit of 64-bit prefix sums.

Reference solution

Python

from typing import List
import bisect

def minOperations(nums: List[int], queries: List[int]) -> List[int]:
    s = sorted(nums)
    n = len(s)
    pre = [0] * (n + 1)
    for i, v in enumerate(s):
        pre[i + 1] = pre[i] + v
    res = []
    for q in queries:
        j = bisect.bisect_left(s, q)
        res.append(q * j - pre[j] + (pre[n] - pre[j]) - q * (n - j))
    return res

Java

public static int[] minOperations(int[] nums, int[] queries) {
    int[] s = nums.clone();
    Arrays.sort(s);
    int n = s.length;
    long[] pre = new long[n + 1];
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + s[i];
    int[] res = new int[queries.length];
    for (int t = 0; t < queries.length; t++) {
        long q = queries[t];
        int lo = 0, hi = n;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (s[mid] < q) lo = mid + 1; else hi = mid;
        }
        res[t] = (int) (q * lo - pre[lo] + (pre[n] - pre[lo]) - q * (n - lo));
    }
    return res;
}

C++

vector<int> minOperations(vector<int>& nums, vector<int>& queries) {
    vector<int> s(nums);
    sort(s.begin(), s.end());
    int n = s.size();
    vector<long long> pre(n + 1, 0);
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + s[i];
    vector<int> res;
    for (int qv : queries) {
        long long q = qv;
        int j = lower_bound(s.begin(), s.end(), qv) - s.begin();
        res.push_back((int)(q * j - pre[j] + (pre[n] - pre[j]) - q * (n - j)));
    }
    return res;
}

JavaScript

var minOperations = function(nums, queries) {
    var s = nums.slice().sort(function(a, b) { return a - b; });
    var n = s.length;
    var pre = [0];
    for (var i = 0; i < n; i++) pre.push(pre[i] + s[i]);
    var res = [];
    for (var t = 0; t < queries.length; t++) {
        var q = queries[t];
        var lo = 0, hi = n;
        while (lo < hi) {
            var mid = (lo + hi) >> 1;
            if (s[mid] < q) lo = mid + 1; else hi = mid;
        }
        res.push(q * lo - pre[lo] + (pre[n] - pre[lo]) - q * (n - lo));
    }
    return res;
};

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