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).
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; }}Video 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.