Problem Description

You have an array nums containing positive integers and an array queries of size m. For each query queries[i], you need to transform all elements in nums to equal queries[i].

You can perform this operation any number of times:

• Increase or decrease any element in the array by 1

Your task is to find the minimum number of operations needed for each query. After processing each query, the array resets to its original state.

For example, if nums = [3, 1, 6, 8] and you want to make all elements equal to 5:

• Change 3 to 5: needs 2 operations (increase by 2)
• Change 1 to 5: needs 4 operations (increase by 4)
• Change 6 to 5: needs 1 operation (decrease by 1)
• Change 8 to 5: needs 3 operations (decrease by 3)
• Total: 2 + 4 + 1 + 3 = 10 operations

The solution uses sorting and prefix sums to efficiently calculate the total operations. After sorting nums, for each query value x:

• Elements less than x need to be increased to x
• Elements greater than x need to be decreased to x
• Binary search finds the boundary between these two groups
• Prefix sums help calculate the total difference quickly

The formula for the minimum operations is:

• For elements greater than x: sum of those elements - (count × x)
• For elements less than x: (count × x) - sum of those elements

Return an array where answer[i] represents the minimum operations needed for queries[i].

Intuition

The key insight is that to transform all elements to a target value, we need to calculate the total "distance" all elements must travel. Each element's contribution to the total operations is simply |element - target|.

Initially, we might think to iterate through the array for each query and sum up these absolute differences. However, this would be inefficient with time complexity O(m × n).

The breakthrough comes from recognizing that we can split the problem into two parts:

1. Elements smaller than the target need to move up
2. Elements larger than the target need to move down

If we sort the array first, all elements less than the target will be on the left side, and all elements greater than the target will be on the right side. This natural partition allows us to use binary search to find the split point efficiently.

For the elements that need to increase (left side), the total operations would be: target × count_of_smaller_elements - sum_of_smaller_elements

For the elements that need to decrease (right side), the total operations would be: sum_of_larger_elements - target × count_of_larger_elements

To avoid recalculating sums repeatedly, we precompute a prefix sum array. This allows us to get the sum of any range in O(1) time.

The elegance of this approach is that sorting the array once enables us to:

• Use binary search to find boundaries in O(log n) time
• Use prefix sums to calculate range sums in O(1) time
• Process each query in O(log n) time instead of O(n)

This reduces the overall complexity from O(m × n) to O(n log n + m log n), making it much more efficient for large inputs.

Learn more about Binary Search, Prefix Sum and Sorting patterns.

Solution Approach

Let's walk through the implementation step by step:

Step 1: Sort the array and build prefix sum

nums.sort()
s = list(accumulate(nums, initial=0))

We first sort nums in ascending order. Then we build a prefix sum array s where s[i] represents the sum of the first i elements. The initial=0 parameter ensures s[0] = 0, making the array length n+1.

Step 2: Process each query

For each query value x, we need to find two critical points using binary search:

i = bisect_left(nums, x + 1)

This finds the first index where nums[i] >= x + 1, meaning all elements from index i onwards are strictly greater than x. These elements need to be decreased to x.

The cost for decreasing these elements is:

t = s[-1] - s[i] - (len(nums) - i) * x

• s[-1] - s[i] gives the sum of all elements from index i to the end
• (len(nums) - i) * x is what their sum should be after changing them all to x
• The difference is the total operations needed

Step 3: Handle elements less than x

i = bisect_left(nums, x)

This finds the first index where nums[i] >= x, meaning all elements before index i are strictly less than x. These elements need to be increased to x.

The cost for increasing these elements is:

t += x * i - s[i]

• x * i is what the sum of the first i elements should be after changing them to x
• s[i] is their current sum
• The difference is the operations needed

Step 4: Combine results

The total operations for query x is the sum of both costs. We append this to our answer array and continue with the next query.

Time Complexity Analysis:

• Sorting: O(n log n)
• Building prefix sum: O(n)
• For each query: O(log n) for binary searches
• Total: O(n log n + m log n) where m is the number of queries

Space Complexity: O(n) for the prefix sum array

The beauty of this solution lies in preprocessing the data (sorting and prefix sums) to enable efficient query processing through binary search, avoiding the naive O(m × n) approach.

Example Walkthrough

Let's walk through a concrete example with nums = [3, 1, 6, 8] and queries = [5, 2].

Initial Setup:

1. Sort nums: [1, 3, 6, 8]
2. Build prefix sum array: s = [0, 1, 4, 10, 18]
   • s[0] = 0
   • s[1] = 0 + 1 = 1
   • s[2] = 1 + 3 = 4
   • s[3] = 4 + 6 = 10
   • s[4] = 10 + 8 = 18

Query 1: x = 5

First, find elements greater than 5:

• bisect_left(nums, 6) returns index 2
• Elements at indices 2 and 3 (values 6 and 8) need to decrease to 5
• Sum of these elements: s[4] - s[2] = 18 - 4 = 14
• After transformation they should sum to: 2 × 5 = 10
• Operations needed: 14 - 10 = 4

Next, find elements less than 5:

• bisect_left(nums, 5) returns index 2
• Elements at indices 0 and 1 (values 1 and 3) need to increase to 5
• These elements should sum to: 2 × 5 = 10
• Current sum: s[2] = 4
• Operations needed: 10 - 4 = 6

Total operations: 4 + 6 = 10

Query 2: x = 2

Find elements greater than 2:

• bisect_left(nums, 3) returns index 1
• Elements at indices 1, 2, 3 (values 3, 6, 8) need to decrease to 2
• Sum of these elements: s[4] - s[1] = 18 - 1 = 17
• After transformation they should sum to: 3 × 2 = 6
• Operations needed: 17 - 6 = 11

Find elements less than 2:

• bisect_left(nums, 2) returns index 1
• Element at index 0 (value 1) needs to increase to 2
• This element should sum to: 1 × 2 = 2
• Current sum: s[1] = 1
• Operations needed: 2 - 1 = 1

Total operations: 11 + 1 = 12

Final Answer: [10, 12]

The algorithm efficiently calculates these totals using binary search to partition the sorted array and prefix sums to compute range sums in constant time.

Solution Implementation

Time and Space Complexity

Time Complexity: O((n + m) × log n) where n is the length of nums and m is the length of queries.

• Sorting nums takes O(n log n) time
• Building the prefix sum array using accumulate takes O(n) time
• For each query in queries (m iterations):
  • Two bisect_left operations, each taking O(log n) time
  • Constant time arithmetic operations
  • Total per query: O(log n)
• Overall: O(n log n + n + m × log n) = O((n + m) × log n)

Note: The reference answer shows O(n × log n), which appears to be considering only the case where m ≈ n or focusing primarily on the sorting complexity when n dominates.

Space Complexity: O(n)

• The sorted nums array is modified in-place (no extra space)
• The prefix sum array s requires O(n + 1) = O(n) space
• The answer array ans requires O(m) space, but this is typically considered output space
• Other variables (i, t, x) use O(1) space
• Overall auxiliary space: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing Binary Search Boundaries

One of the most common mistakes is misunderstanding what bisect_left(nums, x) and bisect_left(nums, x + 1) actually return, leading to incorrect index calculations.

The Pitfall:

# INCORRECT: Using bisect_right for elements greater than x
right_index = bisect_right(nums, x)  # This gives wrong boundary!

Why it's wrong: bisect_right(nums, x) returns the insertion point AFTER all elements equal to x. If there are elements equal to x in the array, they don't need any operations, but this approach would incorrectly include them in the calculation for elements that need to be decreased.

The Solution:

# CORRECT: Use bisect_left with x + 1
right_index = bisect_left(nums, x + 1)

This correctly identifies the first element strictly greater than x.

2. Off-by-One Errors in Prefix Sum Indexing

The Pitfall:

# INCORRECT: Forgetting that prefix_sums has length n+1
prefix_sums = list(accumulate(nums))  # No initial=0
# Later trying to use prefix_sums[i] incorrectly

Why it's wrong: Without initial=0, the prefix sum array has length n instead of n+1, making index calculations confusing and error-prone.

The Solution:

# CORRECT: Always use initial=0 for cleaner indexing
prefix_sums = list(accumulate(nums, initial=0))
# Now prefix_sums[i] represents sum of first i elements

3. Forgetting to Sort the Array

The Pitfall:

def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:
    # INCORRECT: Directly using unsorted array
    prefix_sums = list(accumulate(nums, initial=0))
    # Binary search won't work correctly!

Why it's wrong: Binary search requires a sorted array. Using it on an unsorted array gives meaningless results.

The Solution:

# CORRECT: Always sort first
nums.sort()
prefix_sums = list(accumulate(nums, initial=0))

4. Integer Overflow in Large Datasets

The Pitfall: While Python handles big integers automatically, in other languages or when optimizing:

# Potential issue in languages with fixed integer sizes
total = sum_of_elements - count * target  # Could overflow

The Solution: In Python this isn't an issue, but be aware when porting to other languages. Use appropriate data types (like long long in C++) or check for overflow conditions.

5. Misunderstanding the Problem Requirements

The Pitfall:

# INCORRECT: Modifying the original array
nums.sort()
# Process queries...
# Forgetting that each query should work on the ORIGINAL array state

Why it's wrong: The problem states the array resets after each query. However, sorting doesn't affect the solution since we're calculating absolute differences.

The Solution: The current approach is actually correct because:

• We only need the total operations count
• The order doesn't matter for calculating |nums[i] - target|
• Sorting helps optimize the calculation but doesn't change the result

6. Inefficient Calculation Without Binary Search

The Pitfall:

# INCORRECT: Naive O(n) calculation for each query
for target in queries:
    operations = sum(abs(num - target) for num in nums)

Why it's wrong: While this gives the correct answer, it's O(m × n) time complexity, which is inefficient for large inputs.

The Solution: Use the binary search approach with prefix sums to achieve O(m log n) complexity after O(n log n) preprocessing.