Watch 10 video solutions for Minimum Operations to Make All Array Elements Equal, a medium level problem involving Array, Binary Search, Sorting. This walkthrough by Aryan Mittal has 8,273 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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] <= 109Problem 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 | 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 |