Minimum Operations to Make All Array Elements Equal
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
A straightforward approach where for each query, we iterate through the entire nums array. We calculate the absolute difference between each element and the query value and sum them up. This gives the total operations for that query.
Algorithm
- Initialize an answer list
ansof the same size asqueries. - For each query
qat indexiinqueries:- Initialize a variable
current_operationsto 0. - For each number
numinnums:- Add the absolute difference
abs(num - q)tocurrent_operations.
- Add the absolute difference
- Store
current_operationsinans[i].
- Initialize a variable
- Return
ans.
Walkthrough
The problem asks for the minimum operations to make all elements in nums equal to a given query value q. The minimum number of operations to change a number a to b is |a - b|.
Therefore, for each query q, the total operations is the sum of |nums[i] - q| for all i.
The brute-force method directly implements this calculation. We loop through each query in the queries array. Inside this loop, we have another loop that iterates through every number in the nums array.
For each number num in nums, we compute abs(num - q) and add it to a running total for the current query.
After iterating through all numbers in nums, the running total is the answer for the query q, which we store in our result array.
The nums array is conceptually "reset" for each query, which is naturally handled by this approach as we always read from the original nums array.
class Solution { public List<Long> minOperations(int[] nums, int[] queries) { int m = queries.length; List<Long> answer = new ArrayList<>(); for (int i = 0; i < m; i++) { long currentOps = 0; int q = queries[i]; for (int num : nums) { currentOps += Math.abs(num - q); } answer.add(currentOps); } return answer; }}Complexity
Time
O(m * n), where `m` is the number of queries and `n` is the number of elements in `nums`. For each of the `m` queries, we perform a linear scan of the `n` elements.
Space
O(m) to store the answer list. If the output array is not considered, the space complexity is O(1).
Trade-offs
Pros
Simple to understand and implement.
Cons
Very inefficient for large inputs.
Will result in a 'Time Limit Exceeded' error for the given constraints (
n, m <= 10^5).
This approach optimizes the calculation by first sorting the nums array. For each query q, we can split the nums array into two parts: elements less than or equal to q, and elements greater than q. The total operations can be calculated efficiently using prefix sums.
Algorithm
- Sort the
numsarray. - Create a prefix sum array
prefixof sizen+1.prefix[i]will store the sum of the firstielements of the sortednums. - Initialize an answer list
ans. - For each query
qinqueries:- Use binary search (e.g.,
upper_bound) to find the indexkin the sortednumsarray.kis the number of elements less than or equal toq. - The sum of these
kelements isprefix[k]. - The cost to make these
kelements equal toqis(long)q * k - prefix[k]. - The sum of the remaining
n-kelements isprefix[n] - prefix[k]. - The cost to make these
n-kelements equal toqis(prefix[n] - prefix[k]) - (long)q * (n - k). - The total cost is the sum of these two costs. Add it to
ans.
- Use binary search (e.g.,
- Return
ans.
Walkthrough
The core idea is to avoid re-calculating the sum for each query. The sum Σ|nums[i] - q| can be split based on whether nums[i] is smaller or larger than q.
If we sort nums, all elements smaller than q will appear before all elements larger than q.
Let the sorted array be s_nums. The sum becomes Σ(q - s_nums[i]) for s_nums[i] <= q and Σ(s_nums[i] - q) for s_nums[i] > q.
This can be rewritten as: (k * q - sum_smaller) + (sum_larger - (n-k) * q), where k is the count of elements <= q, sum_smaller is their sum, and sum_larger is the sum of the rest.
To get k, sum_smaller, and sum_larger quickly, we can:
- Sort
numsonce. - Precompute a prefix sum array on the sorted
nums.prefix[i]stores the sum of the firstielements. - For each query
q, use binary search on the sortednumsto find the indexk(the insertion point), which tells us how many elements are less than or equal toq. - With
kand the prefix sum array, we can findsum_smaller(prefix[k]) andsum_larger(prefix[n] - prefix[k]) in O(1) time and calculate the total operations.
class Solution { public List<Long> minOperations(int[] nums, int[] queries) { int n = nums.length; Arrays.sort(nums); long[] prefixSum = new long[n + 1]; for (int i = 0; i < n; i++) { prefixSum[i + 1] = prefixSum[i] + nums[i]; } List<Long> answer = new ArrayList<>(); for (int q : queries) { int k = findInsertionPoint(nums, q); // Binary search long leftSum = prefixSum[k]; long rightSum = prefixSum[n] - prefixSum[k]; long leftCost = (long)q * k - leftSum; long rightCost = rightSum - (long)q * (n - k); answer.add(leftCost + rightCost); } return answer; } // Helper to find number of elements <= target private int findInsertionPoint(int[] arr, int target) { int left = 0, right = arr.length; while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] <= target) { left = mid + 1; } else { right = mid; } } return left; }}Complexity
Time
O(n log n + m log n). Sorting `nums` takes O(n log n). Building the prefix sum array takes O(n). Each of the `m` queries involves a binary search, taking O(log n).
Space
O(n + m). O(n) for the prefix sum array and O(m) for the result list.
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Can pass the given constraints.
Cons
The repeated binary searches can be optimized further if queries are also sorted.
This is a refinement of the previous approach. Instead of performing a binary search for each query, we can sort the queries as well. By processing the queries in sorted order, we can find the split point in the nums array using a two-pointer technique, which is more efficient than repeated binary searches.
Algorithm
- Sort the
numsarray. - Create a prefix sum array
prefixfor the sortednums. - Create a 2D array or a list of objects
queryPairsto store each query's value and its original index. - Sort
queryPairsbased on the query values. - Initialize an answer array
ansof sizem. - Initialize a pointer
k = 0for thenumsarray. - For each sorted query
(q, original_index)inqueryPairs:- Advance the pointer
kwhilek < nandnums[k] <= q. - Now,
kis the count of elements innumsthat are less than or equal toq. - Calculate the total operations using the prefix sum formula:
cost = (q * k - prefix[k]) + ((prefix[n] - prefix[k]) - q * (n - k)). - Store the
costinans[original_index].
- Advance the pointer
- Return
ansas a list.
Walkthrough
This approach builds upon the idea of sorting nums and using prefix sums. The key optimization is how we handle the queries.
First, we sort nums and compute its prefix sums, just like in the previous approach.
Then, instead of processing queries in their original order, we pair each query with its original index and sort these pairs based on the query value.
We then iterate through the sorted queries. We use a pointer, say k, to keep track of our position in the sorted nums array.
As we move from a smaller query q_i to a larger query q_{i+1}, the split point in nums (the index where elements become larger than the query value) can only stay the same or move to the right.
Therefore, for each query, we don't need to restart a search from the beginning of nums. We can simply advance the pointer k from its last position until we find the new split point.
Over the course of iterating through all m queries, the pointer k will traverse the nums array at most once. This amortizes the cost of finding the split point to O(n+m) for all queries combined.
After calculating the operations for a sorted query, we place the result in the final answer array at its original index.
class Solution { public List<Long> minOperations(int[] nums, int[] queries) { int n = nums.length; int m = queries.length; Arrays.sort(nums); long[] prefixSum = new long[n + 1]; for (int i = 0; i < n; i++) { prefixSum[i + 1] = prefixSum[i] + nums[i]; } int[][] queryPairs = new int[m][2]; for (int i = 0; i < m; i++) { queryPairs[i][0] = queries[i]; queryPairs[i][1] = i; } Arrays.sort(queryPairs, (a, b) -> Integer.compare(a[0], b[0])); long[] answer = new long[m]; int k = 0; for (int i = 0; i < m; i++) { int q = queryPairs[i][0]; int originalIndex = queryPairs[i][1]; while (k < n && nums[k] <= q) { k++; } long leftSum = prefixSum[k]; long rightSum = prefixSum[n] - prefixSum[k]; long leftCost = (long)q * k - leftSum; long rightCost = rightSum - (long)q * (n - k); answer[originalIndex] = leftCost + rightCost; } List<Long> result = new ArrayList<>(); for (long val : answer) { result.add(val); } return result; }}Complexity
Time
O(n log n + m log m). Sorting `nums` is O(n log n). Sorting queries is O(m log m). The two-pointer traversal over `nums` and `queries` takes O(n + m). The dominant factors are the sorting steps.
Space
O(n + m). O(n) for the prefix sum array, O(m) for storing query pairs, and O(m) for the result.
Trade-offs
Pros
The most efficient approach, especially when
nandmare large.It avoids the logarithmic factor associated with repeated binary searches for each query.
Cons
Slightly more complex to implement due to the need to handle original query indices.
Solutions
Solution
class Solution {public List<Long> minOperations(int[] nums, int[] queries) { Arrays.sort(nums); int n = nums.length; long[] s = new long[n + 1]; for (int i = 0; i < n; ++i) { s[i + 1] = s[i] + nums[i]; } List<Long> ans = new ArrayList<>(); for (int x : queries) { int i = search(nums, x + 1); long t = s[n] - s[i] - 1L * (n - i) * x; i = search(nums, x); t += 1L * x * i - s[i]; ans.add(t); } return ans; }private int search(int[] nums, int x) { int l = 0, r = nums.length; while (l < r) { int mid = (l + r) >> 1; if (nums[mid] >= x) { r = mid; } else { l = mid + 1; } } return l; }}class Solution {public: vector<long long> minOperations(vector<int> &nums, vector<int> &queries) { sort(nums.begin(), nums.end()); int n = nums.size(); vector<long long> s(n + 1); for (int i = 0; i < n; ++i) { s[i + 1] = s[i] + nums[i]; } vector<long long> ans; for (auto &x : queries) { int i = lower_bound(nums.begin(), nums.end(), x + 1) - nums.begin(); long long t = s[n] - s[i] - 1LL * (n - i) * x; i = lower_bound(nums.begin(), nums.end(), x) - nums.begin(); t += 1LL * x * i - s[i]; ans.push_back(t); } return ans; }};class Solution: def minOperations(self, nums: List[int], queries: List[int]) -> List[int]: nums . sort() s = list(accumulate(nums, initial=0)) ans = [] for x in queries: i = bisect_left(nums, x + 1) t = s[- 1] - s[i] - (len(nums) - i) * x i = bisect_left(nums, x) t += x * i - s[i] ans . append(t) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.