# Minimum Operations to Make All Array Elements Equal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-operations-to-make-all-array-elements-equal)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-make-all-array-elements-equal
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [IBM](https://scaleengineer.com/companies/ibm), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan)
---
## Problem
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.length`
* `m == queries.length`
* `1 <= n, m <= 105`
* `1 <= nums[i], queries[i] <= 109`

# Approaches
## Brute Force Iteration
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.
**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).
**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`).
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize an answer list `ans` of the same size as `queries`.
- For each query `q` at index `i` in `queries`:
    - Initialize a variable `current_operations` to 0.
    - For each number `num` in `nums`:
        - Add the absolute difference `abs(num - q)` to `current_operations`.
    - Store `current_operations` in `ans[i]`.
- Return `ans`.

## Sorting with Prefix Sums and Binary Search
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.
**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.
**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.
### Explanation
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:
1. Sort `nums` once.
2. Precompute a prefix sum array on the sorted `nums`. `prefix[i]` stores the sum of the first `i` elements.
3. For each query `q`, use binary search on the sorted `nums` to find the index `k` (the insertion point), which tells us how many elements are less than or equal to `q`.
4. With `k` and the prefix sum array, we can find `sum_smaller` (`prefix[k]`) and `sum_larger` (`prefix[n] - prefix[k]`) in O(1) time and calculate the total operations.

```java
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;
    }
}
```
### Algorithm
- Sort the `nums` array.
- Create a prefix sum array `prefix` of size `n+1`. `prefix[i]` will store the sum of the first `i` elements of the sorted `nums`.
- Initialize an answer list `ans`.
- For each query `q` in `queries`:
    - Use binary search (e.g., `upper_bound`) to find the index `k` in the sorted `nums` array. `k` is the number of elements less than or equal to `q`.
    - The sum of these `k` elements is `prefix[k]`.
    - The cost to make these `k` elements equal to `q` is `(long)q * k - prefix[k]`.
    - The sum of the remaining `n-k` elements is `prefix[n] - prefix[k]`.
    - The cost to make these `n-k` elements equal to `q` is `(prefix[n] - prefix[k]) - (long)q * (n - k)`.
    - The total cost is the sum of these two costs. Add it to `ans`.
- Return `ans`.

## Optimal Approach with Two Pointers
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.
**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.
**Pros:** The most efficient approach, especially when `n` and `m` are 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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Sort the `nums` array.
- Create a prefix sum array `prefix` for the sorted `nums`.
- Create a 2D array or a list of objects `queryPairs` to store each query's value and its original index.
- Sort `queryPairs` based on the query values.
- Initialize an answer array `ans` of size `m`.
- Initialize a pointer `k = 0` for the `nums` array.
- For each sorted query `(q, original_index)` in `queryPairs`:
    - Advance the pointer `k` while `k < n` and `nums[k] <= q`.
    - Now, `k` is the count of elements in `nums` that are less than or equal to `q`.
    - Calculate the total operations using the prefix sum formula: `cost = (q * k - prefix[k]) + ((prefix[n] - prefix[k]) - q * (n - k))`.
    - Store the `cost` in `ans[original_index]`.
- Return `ans` as a list.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```