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.
- Difficulty: Medium
- Topics: Arrays, Sorting, Binary Search, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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.lengthm == queries.length1 <= n, m <= 10^51 <= nums[i], queries[i] <= 10^4
Hints for Minimum Operations to Make All Array Elements Equal
Hint 1
The answer for target
qisΣ |nums[i] - q|— the order ofnumsdoes not matter, so sort it.Hint 2
In sorted order the elements below
qform a prefix and the rest a suffix; their contributions areq · count - sumandsum - q · count.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
- Sort
numsand buildpre[i]= sum of the firstisorted values. - For a query
q, letjbe the number of elements smaller thanq(lower bound ofq). - Raising the small ones costs
q · j - pre[j]; lowering the rest costs(pre[n] - pre[j]) - q · (n - j). - 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
qcost 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 resJava
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