Solution: Minimum Operations to Make All Array Elements Equal

Statement

You are given an array, nums, consisting of positive integers of size n and another array queries of size m. For each query $i$ in queries, the goal is to make all elements of nums equal to queries[i]. To achieve this, you can perform the following operation any number of times:

• Increase or decrease an element of nums by 1.

Return an array answer of size m, where answer[i] is the minimum number of operations needed to make all elements of nums equal to queries[i]. After processing each query, the nums array is reset to its original state.

Constraints

• n $==$ nums.length

• m $==$ queries.length

• $1 \leq$ n, m $\leq 10^3$

• $1 \leq$ nums[i], queries[i] $\leq 10^5$

Solution

The algorithm efficiently calculates the minimum operations needed to adjust an array (nums) to match a series of query values. It sorts the array and uses a prefix sum array for efficient range sum calculations. The prefix sum array stores the cumulative sums of the sorted nums array and is computed by iterating through the array and maintaining a running total. For each query, the algorithm splits the array into elements smaller than and greater than or equal to the query using binary search. The binary search helps find the smallest index where the element is greater than or equal to the query value. The range is adjusted during the search: if the middle element is smaller than the query, the search moves to the right half; if it is greater than or equal to the query, the search continues in the left half. The cost is then computed as the sum of two parts:

1. Left cost: The operations needed to increase all smaller elements to the query value.
   $\text{Left Cost} = (\text{query} \times \text{count of smaller elements}) - \text{sum of smaller elements}$

2. Right cost: The operations needed to decrease all larger elements to the query value.
   $\text{Right Cost} = (\text{sum of larger elements}) - (\text{query} \times \text{count of larger elements})$

The total cost for each query is the sum of the left and right costs, and the results are returned for all queries.

The steps of the algorithm are as follows:

1. Sort the nums array to enable efficient binary search and prefix sum calculations. Sorting allows quick identification of elements smaller than or greater than or equal to a query value.

2. Construct a prefix sum array prefix where prefix[i] stores the cumulative sum of the first i elements of the sorted nums. This allows efficient computation of the sum of any subarray in constant time.

3. For each query, use a binary search to find the smallest index idx such that nums[idx] >= query. This divides the array into two parts:

• Left part: Elements smaller than the query (nums[0] to nums[idx-1]).

• Right part: Elements greater than or equal to the query (nums[idx] to nums[n-1]).

4. Compute the operations required for both parts of the array. The total cost for the query is the sum of the left and right costs:

• Left operations: Adjust all elements in the left part to the query value.

  • Left cost = (query × idx) − prefix[idx]

  • Here, query × idx represents the total value if all idx elements are set to query, and prefix[idx] is the actual sum of these elements.

• Right operations: Adjust all elements in the right part to the query value.

  • Right cost = (prefix[n] − prefix[idx]) − (query × (n − idx))

  • Here, prefix[n] − prefix[idx] is the sum of elements from idx to the end of the array, and query × (n − idx) is the target value for these elements.

5. Append the total cost for the query to the result list.

6. After processing all queries, return the result list containing the costs for each query.

Let’s look at the following illustration to get a better understanding of the solution: