Minimum Operations to Make All Array Elements Equal solution and explanation
IBM
9 more videos on this problem
Minimum Operations to Make All Array Elements Equal || Binary Search || Prefix Sums || Leetcode 2602Aryan Mittal · 19:57 · 8K views
2602. Minimum Operations to Make All Array Elements Equal - LEETCODE WEEKLY CONTEST 338 (Logic)Joyjit Codes · 6:20 · 2K views
2602. Minimum Operations to Make All Array Elements Equal (Leetcode Medium)Programming Live with Larry · 22:16 · 1K views
Leetcode 2602. Minimum Operations to Make All Array Elements EqualElite Code · 34:00 · 783 views
Minimum Operations to Make All Array Elements Equal | Weekly Contest 338 | Leetcode 2602OffCampus Phodenge | Aman Chowdhury · 17:21 · 435 views
[Eng] Leetcode Weekly Contest 338 | 2602. Minimum Operations to Make All Array Elements EqualCyCode · 11:03 · 306 views
2602. Minimum Operations to Make All Array Elements EqualLeetcode and Interview Question · 20:47 · 121 views
2602. Minimum Operations to Make All Array Elements Equal || LeetCode ||Weekly Contest 338 SubscribeCodeCake · 0:16 · 118 views
2602. Minimum Operations to Make All Array Elements Equal | Medium | LeetCode | No Talking.Optimization · 10:51 · 74 views
leetcode 2602. Minimum Operations to Make All Array Elements Equal - partial sum + binary searchCode-Yao · 22:07 · 65 views
The problem
You are given an array nums consisting of positive integers.
You are also given an integer array queries of size m. For the ith query, you want to make all of the elements of nums equal to queries[i]. You can perform the following operation on the array any number of times:
- Increase or decrease an element of the array by
1.
Return an array answer of size m where answer[i] is the minimum number of operations to make all elements of nums equal to queries[i].
Note that after each query the array is reset to its original state.
Example 1:
Input: nums = [3,1,6,8], queries = [1,5] Output: [14,10] Explanation: For the first query we can do the following operations: - Decrease nums[0] 2 times, so that nums = [1,1,6,8]. - Decrease nums[2] 5 times, so that nums = [1,1,1,8]. - Decrease nums[3] 7 times, so that nums = [1,1,1,1]. So the total number of operations for the first query is 2 + 5 + 7 = 14. For the second query we can do the following operations: - Increase nums[0] 2 times, so that nums = [5,1,6,8]. - Increase nums[1] 4 times, so that nums = [5,5,6,8]. - Decrease nums[2] 1 time, so that nums = [5,5,5,8]. - Decrease nums[3] 3 times, so that nums = [5,5,5,5]. So the total number of operations for the second query is 2 + 4 + 1 + 3 = 10.
Example 2:
Input: nums = [2,9,6,3], queries = [10] Output: [20] Explanation: We can increase each value in the array to 10. The total number of operations will be 8 + 1 + 4 + 7 = 20.
Constraints:
n == nums.lengthm == queries.length1 <= n, m <= 1051 <= nums[i], queries[i] <= 109
Approach overview
Problem Overview: Given an integer array nums and multiple queries, each query asks for the minimum number of operations required to make every element in the array equal to the query value. One operation increments or decrements an element by 1. The task is to compute the total cost for every query efficiently.
Approach 1: Brute Force (O(n * q) time, O(1) space)
For each query value x, iterate through the entire array and compute the absolute difference |nums[i] - x|. Summing these values gives the total number of operations needed to convert every element to x. This approach is straightforward and useful for understanding the cost model. However, when both n and q grow large, the repeated full-array scans become expensive.
Approach 2: Sorted Array with Prefix Sums (O((n + q) log n) time, O(n) space)
Sort the array first using sorting. After sorting, build a prefix sum array so you can quickly compute sums of elements on either side of a pivot. For each query x, use binary search to find the first index where elements become greater than or equal to x. Elements on the left need increments to reach x, and elements on the right need decrements. Using prefix sums, compute these two costs in constant time per query.
The cost for the left side is x * leftCount - leftSum. The cost for the right side is rightSum - x * rightCount. Adding them gives the total operations required for that query. Sorting allows the array to be split cleanly around the target value, and prefix sums avoid recomputing subarray sums.
Approach 3: Prefix Sums After Sorting (O((n + q) log n) time, O(n) space)
This variation emphasizes precomputation. After sorting the array, build the prefix sum array once. Each query then performs a binary search to locate the partition point and calculates the left and right transformation costs using constant-time prefix sum lookups. The algorithm avoids scanning the array entirely during queries, which makes it scalable for large inputs.
Recommended for interviews: The sorted array with prefix sums approach is what interviewers expect. The brute force method shows you understand the problem definition and cost calculation, but the optimized approach demonstrates skill with array preprocessing, binary search partitioning, and prefix sum optimization.
Approach 1: Approach 1: Brute Force
This approach iterates through each query and calculates the minimum number of operations required for each element of the array to equal the query. It involves a straightforward nested iteration.
def min_operations(nums, queries):
result = []
for query in queries:
operations = sum(abs(num - query) for num in nums)
result.append(operations)
return resultThis Python solution iterates over each query value. For each query, it calculates the sum of the absolute differences between the query and each element in nums. This sum represents the total operations required to make all elements in the array equal to that query value.
The time complexity is O(n*m) where n is the length of nums and m is the length of queries. The space complexity is O(1) as no extra space proportional to the inputs is used.
Approach 2: Approach 2: Sorted Array with Prefix Sums
This optimized approach involves sorting the array and using prefix sums (or cumulative sums) to efficiently compute the number of operations needed. With a prefix sum array, the number of operations to make all elements equal to a query can be obtained more quickly, especially helpful for large datasets.
from bisect import bisect_left
def min_operations(nums, queries):
nums.sort()
prefix_sums = [0]
for num in nums:
prefix_sums.append(prefix_sums[-1] + num)
def operations(target):
idx = bisect_left(nums, target)
less_operations = target * idx - prefix_sums[idx]
more_operations = (prefix_sums[-1] - prefix_sums[idx]) - target * (len(nums) - idx)
return less_operations + more_operations
return [operations(query) for query in queries]This function first sorts the array and constructs a prefix sums array where each index represents the cumulative sum of nums up to that point. For each query, it uses binary search (via bisect_left) to find how many elements are less than the query, then calculates operations needed for those less than and more than the query using prefix sums.
The time complexity is O((n + m) log n) due to sorting and binary search, and the space complexity is O(n) owing to the prefix sums.
Approach 3: Prefix Sums After Sorting
By sorting the array and using prefix sums, we can efficiently compute the total operations needed for each query. This reduces the need for recalculating the sum of differences from scratch for each query.
def min_operations(nums, queries):
nums.sort()
n = len(nums)
prefix_sum = [0] * (n + 1)
for i in range(n):
prefix_sum[i + 1] = prefix_sum[i] + nums[i]
results = []
for query in queries:
l, r = 0, n
while l < r:
mid = (l + r) // 2
if nums[mid] < query:
l = mid + 1
else:
r = mid
left_operations = query * l - prefix_sum[l]
right_operations = (prefix_sum[n] - prefix_sum[l]) - query * (n - l)
results.append(left_operations + right_operations)
return results
# Example usage:
nums = [3, 1, 6, 8]
queries = [1, 5]
print(min_operations(nums, queries)) # Output: [14, 10]#include <vector>
#include <algorithm>
#include <iostream>
std::vector<long long> minOperations(std::vector<int>& nums, std::vector<int>& queries) {
std::sort(nums.begin(), nums.end());
int n = nums.size();
std::vector<long long> prefix_sum(n + 1, 0);
for (int i = 0; i < n; ++i) {
prefix_sum[i + 1] = prefix_sum[i] + nums[i];
}
std::vector<long long> results;
for (int query : queries) {
int l = 0, r = n;
while (l < r) {
int mid = (l + r) / 2;
if (nums[mid] < query) {
l = mid + 1;
} else {
r = mid;
}
}
long long left_operations = static_cast<long long>(query) * l - prefix_sum[l];
long long right_operations = (prefix_sum[n] - prefix_sum[l]) - static_cast<long long>(query) * (n - l);
results.push_back(left_operations + right_operations);
}
return results;
}
int main() {
std::vector<int> nums = {3, 1, 6, 8};
std::vector<int> queries = {1, 5};
std::vector<long long> result = minOperations(nums, queries);
for (long long res : result) {
std::cout << res << " ";
}
return 0;
}This Python solution sorts the nums array and precomputes prefix sums to handle each query in logarithmic time due to the binary search used to find the first element not less than the current query value.
The time complexity of this solution is O(n log n) due to sorting and O(m log n) for each query, where n is the length of the nums array and m is the number of queries. The space complexity is O(n) because of the prefix sum array used for calculations.
Approach 4: Brute Force Approach
While less efficient, a brute-force approach incrementally calculates the number of operations needed to convert all array elements to each query value, iterating through the array for each query.
import java.util.*;
class Solution {
public List<Long> minOperations(int[] nums, int[] queries) {
List<Long> results = new ArrayList<>();
for (int query : queries) {
long totalOperations = 0;
for (int num : nums) {
totalOperations += Math.abs(num - query);
}
results.add(totalOperations);
}
return results;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {3, 1, 6, 8};
int[] queries = {1, 5};
System.out.println(sol.minOperations(nums, queries)); // Output: [14, 10]
}
}using System;
using System.Collections.Generic;
class Solution {
public List<long> MinOperations(int[] nums, int[] queries) {
var results = new List<long>();
foreach (var query in queries) {
long totalOperations = 0;
foreach (var num in nums) {
totalOperations += Math.Abs(num - query);
}
results.Add(totalOperations);
}
return results;
}
static void Main() {
var solution = new Solution();
int[] nums = { 3, 1, 6, 8 };
int[] queries = { 1, 5 };
var result = solution.MinOperations(nums, queries);
Console.WriteLine(string.Join(" ", result)); // Output: 14 10
}
}This Java solution iterates over nums for each query in queries and calculates the total operations needed, summing the absolute differences.
The time complexity is O(n * m), where n is the length of nums and m is the number of queries. The space complexity is O(1) aside from output storage, as no additional data structures are used.
Approach 5: sort + prefix sum + binary search
First, we sort the array nums and calculate the prefix sum array s with a length of n+1, where s[i] represents the sum of the first i elements in the array nums.
Then, we traverse each query queries[i], we need to reduce all elements greater than queries[i] to queries[i], and increase all elements less than queries[i] to queries[i].
We can use binary search to find the index i of the first element in the array nums that is greater than queries[i]. There are n-i elements that need to be reduced to queries[i], and the sum of these elements is s[n]-s[i]. These elements need to be reduced by n-i queries[i], so the total number of operations to reduce these elements to queries[i] is s[n]-s[i]-(n-i)times queries[i].
Similarly, we can find the index i of the first element in the array nums that is greater than or equal to queries[i]. There are i elements that need to be increased to queries[i], and the sum of these elements is s[i]. Therefore, the total number of operations to increase these elements to queries[i] is queries[i]times i-s[i].
Finally, add these two total operation counts together to get the minimum number of operations to change all elements in the array nums to queries[i], that is, ans[i]=s[n]-s[i]-(n-i)times queries[i]+queries[i]times i-s[i].
Time complexity O(n times log n), space complexity O(n), where n is the length of the array nums.
function minOperations(nums: number[], queries: number[]): number[] {
nums.sort((a, b) => a - b);
const n = nums.length;
const s: number[] = new Array(n + 1).fill(0);
for (let i = 0; i < n; ++i) {
s[i + 1] = s[i] + nums[i];
}
const search = (x: number): number => {
let l = 0;
let r = n;
while (l < r) {
const mid = (l + r) >> 1;
if (nums[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
const ans: number[] = [];
for (const x of queries) {
const i = search(x + 1);
let t = s[n] - s[i] - (n - i) * x;
const j = search(x);
t += x * j - s[j];
ans.push(t);
}
return ans;
}func minOperations(nums []int, queries []int) (ans []int64) {
sort.Ints(nums)
n := len(nums)
s := make([]int, n+1)
for i, x := range nums {
s[i+1] = s[i] + x
}
for _, x := range queries {
i := sort.SearchInts(nums, x+1)
t := s[n] - s[i] - (n-i)*x
i = sort.SearchInts(nums, x)
t += x*i - s[i]
ans = append(ans, int64(t))
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force | The time complexity is O(n*m) where n is the length of nums and m is the length of queries. The space complexity is O(1) as no extra space proportional to the inputs is used. |
| Approach 2: Sorted Array with Prefix Sums | The time complexity is O((n + m) log n) due to sorting and binary search, and the space complexity is O(n) owing to the prefix sums. |
| Prefix Sums After Sorting | The time complexity of this solution is O(n log n) due to sorting and O(m log n) for each query, where n is the length of the |
| Brute Force Approach | The time complexity is O(n * m), where n is the length of |
| sort + prefix sum + binary search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n * q) | O(1) | Small inputs or when explaining the base logic during interviews |
| Sorted Array with Prefix Sums | O((n + q) log n) | O(n) | Best general solution when multiple queries must be processed efficiently |
| Prefix Sums After Sorting + Binary Search | O((n + q) log n) | O(n) | Large arrays with many queries where repeated scans would be too slow |
Frequently asked questions
Is Minimum Operations to Make All Array Elements Equal easy or hard?
The problem is rated Medium because the brute force idea is simple but not efficient. The challenge is recognizing that sorting and prefix sums allow you to compute operation costs in constant time after locating the partition with binary search.
Minimum Operations to Make All Array Elements Equal Python/Java solution
Python solutions typically use sorting, prefix sums, and the bisect module for binary search. Java and C++ implementations follow the same logic with arrays and manual binary search or built-in utilities. Each query calculates the cost of adjusting elements on the left and right side of the partition.
How to solve Minimum Operations to Make All Array Elements Equal in O(n)?
Pure O(n) per query is not feasible because queries must consider the distribution of elements around the target value. The closest efficient solution preprocesses the array by sorting and building prefix sums. Each query then uses binary search and constant-time arithmetic, giving O(log n) per query after preprocessing.
What is the best approach for Minimum Operations to Make All Array Elements Equal?
The most efficient approach sorts the array and builds a prefix sum array. For each query, binary search finds the split point where values become greater than the target. Using prefix sums, you compute the cost of increasing smaller elements and decreasing larger elements in O(1). The total complexity becomes O((n + q) log n).
Is Minimum Operations to Make All Array Elements Equal asked at Google/Amazon/Meta?
Problems involving prefix sums, binary search partitioning, and cost minimization appear frequently in interviews at companies like Amazon, Google, and Meta. This specific problem tests the ability to transform a brute force cost calculation into an optimized query-processing algorithm.
What data structure is used in Minimum Operations to Make All Array Elements Equal?
The core structures are a sorted array and a prefix sum array. Binary search is used to partition the array around the query value, and prefix sums allow constant-time computation of subarray totals needed to calculate operation costs.
What is the time complexity of Minimum Operations to Make All Array Elements Equal?
The brute force approach runs in O(n * q) because every query scans the entire array. The optimized solution sorts the array once in O(n log n), then processes each query with binary search and prefix sum calculations in O(log n). The final complexity is O((n + q) log n) with O(n) additional space.