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.
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.
This 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.
Python
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.
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.
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.
Python
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.
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.
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.
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.
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.
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.
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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 |
Minimum Operations to Make All Array Elements Equal || Binary Search || Prefix Sums || Leetcode 2602 • Aryan Mittal • 8,273 views views
Watch 9 more video solutions →Practice Minimum Operations to Make All Array Elements Equal with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor