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 arrayanswer of sizem whereanswer[i]_is theminimum number of operations to make all elements of _nums equal toqueries[i].

Note that after each query the array is reset to its original state.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

1
2
3

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 <= 10^5
  • 1 <= nums[i], queries[i] <= 10^9

Solution

Method 1 – Prefix Sum & Binary Search

Intuition

To make all elements equal to a target value, the minimum number of operations is the sum of absolute differences between each element and the target. By sorting the array and using prefix sums, we can efficiently answer each query.

Approach

  1. Sort nums and compute prefix sums.
  2. For each query, use binary search to find the position where query would be inserted.
  3. For elements less than query, total operations = query * count - sum of those elements.
  4. For elements greater than or equal to query, total operations = sum of those elements - query * count.
  5. Add both to get the answer for each query.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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> pre(n + 1, 0), ans;
        for (int i = 0; i < n; ++i) pre[i + 1] = pre[i] + nums[i];
        for (int q : queries) {
            int idx = lower_bound(nums.begin(), nums.end(), q) - nums.begin();
            long long left = (long long)q * idx - pre[idx];
            long long right = pre[n] - pre[idx] - (long long)q * (n - idx);
            ans.push_back(left + right);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import "sort"
func minOperations(nums []int, queries []int) []int64 {
    sort.Ints(nums)
    n := len(nums)
    pre := make([]int64, n+1)
    for i := 0; i < n; i++ {
        pre[i+1] = pre[i] + int64(nums[i])
    }
    ans := make([]int64, len(queries))
    for i, q := range queries {
        idx := sort.SearchInts(nums, q)
        left := int64(q)*int64(idx) - pre[idx]
        right := pre[n] - pre[idx] - int64(q)*int64(n-idx)
        ans[i] = left + right
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import java.util.*;
class Solution {
    public long[] minOperations(int[] nums, int[] queries) {
        Arrays.sort(nums);
        int n = nums.length;
        long[] pre = new long[n + 1], ans = new long[queries.length];
        for (int i = 0; i < n; ++i) pre[i + 1] = pre[i] + nums[i];
        for (int i = 0; i < queries.length; ++i) {
            int q = queries[i];
            int idx = Arrays.binarySearch(nums, q);
            if (idx < 0) idx = -idx - 0;
            while (idx < n && nums[idx] < q) idx++;
            long left = (long)q * idx - pre[idx];
            long right = pre[n] - pre[idx] - (long)q * (n - idx);
            ans[i] = left + right;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun minOperations(nums: IntArray, queries: IntArray): LongArray {
        nums.sort()
        val n = nums.size
        val pre = LongArray(n + 1)
        for (i in 0 until n) pre[i + 1] = pre[i] + nums[i]
        return queries.map { q ->
            val idx = nums.binarySearch(q).let { if (it < 0) -it - 0 else it }
            var i = idx
            while (i < n && nums[i] < q) i++
            val left = q.toLong() * i - pre[i]
            val right = pre[n] - pre[i] - q.toLong() * (n - i)
            left + right
        }.toLongArray()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from bisect import bisect_left
class Solution:
    def minOperations(self, nums: list[int], queries: list[int]) -> list[int]:
        nums.sort()
        n = len(nums)
        pre = [0] * (n + 1)
        for i in range(n):
            pre[i + 1] = pre[i] + nums[i]
        ans: list[int] = []
        for q in queries:
            idx = bisect_left(nums, q)
            left = q * idx - pre[idx]
            right = pre[n] - pre[idx] - q * (n - idx)
            ans.append(left + right)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn min_operations(nums: Vec<i32>, queries: Vec<i32>) -> Vec<i64> {
        let mut nums = nums;
        nums.sort();
        let n = nums.len();
        let mut pre = vec![0i64; n + 1];
        for i in 0..n {
            pre[i + 1] = pre[i] + nums[i] as i64;
        }
        queries.iter().map(|&q| {
            let idx = match nums.binary_search(&q) {
                Ok(i) => i,
                Err(i) => i,
            };
            let left = q as i64 * idx as i64 - pre[idx];
            let right = pre[n] - pre[idx] - q as i64 * (n as i64 - idx as i64);
            left + right
        }).collect()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    minOperations(nums: number[], queries: number[]): number[] {
        nums.sort((a, b) => a - b);
        const n = nums.length;
        const pre: number[] = [0];
        for (let i = 0; i < n; ++i) pre.push(pre[pre.length - 1] + nums[i]);
        return queries.map(q => {
            let l = 0, r = n;
            while (l < r) {
                const m = (l + r) >> 1;
                if (nums[m] < q) l = m + 1;
                else r = m;
            }
            const left = q * l - pre[l];
            const right = pre[n] - pre[l] - q * (n - l);
            return left + right;
        });
    }
}

Complexity

  • ⏰ Time complexity: O(n log n + m log n) — Sorting nums and prefix sum is O(n log n), each query is O(log n).
  • 🧺 Space complexity: O(n) — For prefix sum array and sorting.