Problem Overview

Given a positive integer array nums and m queries, each query asks for the minimum number of operations to transform all elements in nums to a target value q. One operation allows incrementing or decrementing a single element by 1. The array resets to its original state after each query.

Solution Approach

For each target value, the minimum operations equal the sum of absolute differences between the target and every array element:

$$\text{answer} = \sum_{i=1}^{n} |\text{nums}[i] - q|$$

To compute this efficiently for multiple queries:

1. Sort the array in ascending order
2. Precompute a prefix sum array to enable O(1) range sum queries
3. For each target value, use binary search to find the insertion point
4. Calculate the sum using the prefix sums

Implementation

Java Solution:

class Solution {
    public List<Long> minOperations(int[] nums, int[] queries) {
        int n = nums.length;
        Arrays.sort(nums);
        
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        int m = queries.length;
        List<Long> result = new ArrayList<>(m);
        
        for (int i = 0; i < m; i++) {
            int target = queries[i];
            int pos = binarySearch(nums, target);
            
            long leftSum = (long) target * (pos + 1) - prefix[pos + 1];
            long rightSum = (prefix[n] - prefix[pos + 1]) - (long) target * (n - 1 - pos);
            
            result.add(leftSum + rightSum);
        }
        return result;
    }

    private int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }
}

Python Solution:

class Solution:
    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:
        def find_position(arr, target, low, high):
            while low <= high:
                mid = low + (high - low) // 2
                if arr[mid] < target:
                    low = mid + 1
                else:
                    high = mid - 1
            return high

        n = len(nums)
        nums.sort()
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]

        result = []
        for target in queries:
            idx = find_position(nums, target, 0, n - 1)
            left_part = target * (idx + 1) - prefix[idx + 1]
            right_part = (prefix[n] - prefix[idx + 1]) - target * (n - 1 - idx)
            result.append(left_part + right_part)
        return result

Complexity Analysis

Time Complexity: O((n + m) log n)

• Sorting the array: O(n log n)
• Building prefix sums: O(n)
• For each of m queries: binary search O(log n)

Space Complexity: O(n)

• Prefix sum array requires O(n) extra space
• Output array requires O(m) space

Mathematical Foundation

For a target value t with insertion position pos (all eelments at indices ≤ pos are less than t, all elements at indices > pos are greater than or equal to t):

$$\text{operations} = \underbrace{t \cdot (pos + 1) - \sum_{i=0}^{pos} \text{nums}[i]}{\text{increase left side}} + \underbrace{\sum{i=pos+1}^{n-1} \text{nums}[i] - t \cdot (n - 1 - pos)}_{\text{decrease right side}}$$

This formula efficiently computes the total distance by leveraging prefix sums to calculate range sums in constant time.