LeetCode 2602 - Minimum Operations to Make All Array Elements Equal

The problem gives us an integer array nums and another array queries. For every query value q, we must calculate the minimum number of operations required to make every element in nums equal to q. One operation consists of increasing or decreasing a single element by exactly 1.

leetcodemediumarraybinary-searchsortingprefix-sum

LeetCode Problem 2602

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Sorting, Prefix Sum

Solution

Problem Understanding

The problem gives us an integer array nums and another array queries. For every query value q, we must calculate the minimum number of operations required to make every element in nums equal to q.

One operation consists of increasing or decreasing a single element by exactly 1. Since each operation changes the value by one step, the number of operations needed to convert a value x into q is simply:

|x - q|

For a query q, the total cost is therefore:

sum(|nums[i] - q| for all i)

The important detail is that after processing one query, the array resets to its original state. This means queries are independent from each other. We are not permanently modifying nums.

The constraints are very large:

  • n and m can each be up to 100000
  • Values can be as large as 10^9

A naive solution that loops through the entire array for every query would require:

O(n * m)

In the worst case, this becomes:

100000 * 100000 = 10^10

That is far too slow.

The constraints strongly suggest that we need preprocessing and efficient query handling. Since the problem involves repeated calculations over ordered numeric values, sorting and prefix sums are natural candidates.

Several edge cases are important:

  • Queries smaller than every number in nums
  • Queries larger than every number in nums
  • Queries exactly matching existing values
  • Arrays containing duplicate values
  • Arrays of size 1
  • Very large values that may overflow 32-bit integers in some languages

The problem guarantees that all numbers are positive integers and that both arrays are non-empty.

Approaches

Brute Force Approach

The simplest solution is to process each query independently.

For every query q, iterate through every number in nums and compute:

abs(nums[i] - q)

Add all these differences together and store the result.

This works because the minimum number of operations required to transform a number into another number is exactly their absolute difference.

However, this approach performs a full scan of nums for every query.

If:

  • n = 100000
  • m = 100000

then the total operations become:

O(n * m) = O(10^10)

which is too slow.

Optimal Approach

The key observation is that after sorting the array, all numbers smaller than a query contribute in one predictable way, and all numbers larger than the query contribute in another predictable way.

Suppose the query is q.

For all numbers smaller than q:

cost = q - nums[i]

For all numbers larger than q:

cost = nums[i] - q

If the array is sorted, we can use binary search to find the dividing point between:

  • values < q
  • values >= q

Once we know how many elements are on each side, prefix sums allow us to compute total contributions in constant time.

For the left side:

q * countLeft - sumLeft

For the right side:

sumRight - q * countRight

This reduces each query from O(n) to O(log n) because of binary search.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n × m) O(1) Computes absolute difference for every element and every query
Optimal O(n log n + m log n) O(n) Uses sorting, prefix sums, and binary search

Algorithm Walkthrough

Step 1: Sort the Array

Sort nums in ascending order.

This is important because binary search only works on sorted data. Sorting also groups smaller and larger values together, making range calculations easy.

Example:

nums = [3,1,6,8]
sorted = [1,3,6,8]

Step 2: Build a Prefix Sum Array

Create a prefix sum array where:

prefix[i]

stores the sum of the first i elements.

We usually make the prefix array size n + 1 so that:

prefix[0] = 0

Example:

nums   = [1,3,6,8]
prefix = [0,1,4,10,18]

Meaning:

  • first 0 elements sum to 0
  • first 1 element sums to 1
  • first 2 elements sum to 4
  • first 3 elements sum to 10
  • first 4 elements sum to 18

This allows constant-time range sum calculations.

Step 3: Process Each Query

For each query q, use binary search to find the first index where:

nums[index] >= q

This index splits the array into:

  • left side: values smaller than q
  • right side: values greater than or equal to q

Suppose:

index = k

Then:

  • left count = k
  • right count = n - k

Step 4: Compute Left Contribution

All values on the left must be increased to q.

Their total cost is:

(q * leftCount) - leftSum

where:

leftSum = prefix[k]

Step 5: Compute Right Contribution

All values on the right must be decreased to q.

Their total cost is:

rightSum - (q * rightCount)

where:

rightSum = prefix[n] - prefix[k]

Step 6: Add Both Costs

The answer for the query is:

leftCost + rightCost

Store it in the result array.

Why it works

The algorithm works because absolute differences can be separated into two linear forms once the array is sorted.

For elements smaller than q:

|x - q| = q - x

For elements larger than q:

|x - q| = x - q

Sorting allows us to identify these two groups efficiently with binary search. Prefix sums then allow fast computation of total sums for each group. Since every element contributes independently to the total operation count, summing these contributions produces the exact minimum number of operations.

Python Solution

from bisect import bisect_left
from typing import List

class Solution:
    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)

        prefix = [0] * (n + 1)

        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]

        result = []

        total_sum = prefix[n]

        for query in queries:
            index = bisect_left(nums, query)

            left_count = index
            right_count = n - index

            left_sum = prefix[index]
            right_sum = total_sum - left_sum

            left_cost = query * left_count - left_sum
            right_cost = right_sum - query * right_count

            result.append(left_cost + right_cost)

        return result

The implementation begins by sorting nums. This enables binary search and clean separation of values smaller and larger than each query.

Next, the prefix sum array is constructed. Each entry stores the cumulative sum up to that point, allowing constant-time range sum retrieval.

For every query, bisect_left finds the first position where the query could be inserted while maintaining sorted order. This position divides the array into two logical regions.

The left region contains values smaller than the query. Those values need to be increased, so their total adjustment cost is computed using:

query * left_count - left_sum

The right region contains values greater than or equal to the query. Those values need to be decreased, so their total adjustment cost is:

right_sum - query * right_count

Adding both costs gives the minimum operations required for that query.

Go Solution

package main

import (
	"sort"
)

func minOperations(nums []int, queries []int) []int64 {
	sort.Ints(nums)

	n := len(nums)

	prefix := make([]int64, n+1)

	for i := 0; i < n; i++ {
		prefix[i+1] = prefix[i] + int64(nums[i])
	}

	totalSum := prefix[n]

	result := make([]int64, 0, len(queries))

	for _, query := range queries {
		index := sort.SearchInts(nums, query)

		leftCount := int64(index)
		rightCount := int64(n - index)

		leftSum := prefix[index]
		rightSum := totalSum - leftSum

		leftCost := int64(query)*leftCount - leftSum
		rightCost := rightSum - int64(query)*rightCount

		result = append(result, leftCost+rightCost)
	}

	return result
}

The Go implementation follows the same algorithmic structure as the Python version.

One important difference is integer handling. Since the total operation count can exceed the 32-bit integer range, all prefix sums and operation calculations use int64.

Go uses sort.SearchInts instead of Python's bisect_left for binary search.

The result slice is initialized with capacity equal to the number of queries for efficient appends.

Worked Examples

Example 1

nums = [3,1,6,8]
queries = [1,5]

Step 1: Sort nums

nums = [1,3,6,8]

Step 2: Build prefix sums

Index Prefix Sum
0 0
1 1
2 4
3 10
4 18

Query = 1

Binary search:

index = 0

No values are smaller than 1.

Variable Value
leftCount 0
rightCount 4
leftSum 0
rightSum 18

Compute costs:

leftCost = 1 * 0 - 0 = 0
rightCost = 18 - (1 * 4) = 14

Answer:

14

Query = 5

Binary search:

index = 2

Values smaller than 5 are [1,3].

Variable Value
leftCount 2
rightCount 2
leftSum 4
rightSum 14

Compute costs:

leftCost = 5 * 2 - 4 = 6
rightCost = 14 - (5 * 2) = 4

Answer:

10

Final output:

[14,10]

Example 2

nums = [2,9,6,3]
queries = [10]

Step 1: Sort nums

nums = [2,3,6,9]

Step 2: Prefix sums

Index Prefix Sum
0 0
1 2
2 5
3 11
4 20

Query = 10

Binary search:

index = 4

All values are smaller than 10.

Variable Value
leftCount 4
rightCount 0
leftSum 20
rightSum 0

Compute costs:

leftCost = 10 * 4 - 20 = 20
rightCost = 0

Final answer:

20

Complexity Analysis

Measure Complexity Explanation
Time O(n log n + m log n) Sorting takes O(n log n), each query uses binary search in O(log n)
Space O(n) Prefix sum array requires linear extra space

The dominant preprocessing cost is sorting the array. After sorting, every query can be answered independently in logarithmic time using binary search and constant-time prefix sum calculations. This is efficient enough for the maximum constraint sizes.

Test Cases

from typing import List

class Solution:
    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:
        from bisect import bisect_left

        nums.sort()
        n = len(nums)

        prefix = [0] * (n + 1)

        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]

        total_sum = prefix[n]

        result = []

        for query in queries:
            index = bisect_left(nums, query)

            left_count = index
            right_count = n - index

            left_sum = prefix[index]
            right_sum = total_sum - left_sum

            left_cost = query * left_count - left_sum
            right_cost = right_sum - query * right_count

            result.append(left_cost + right_cost)

        return result

solution = Solution()

# Provided example 1
assert solution.minOperations([3,1,6,8], [1,5]) == [14,10]

# Provided example 2
assert solution.minOperations([2,9,6,3], [10]) == [20]

# Single element array
assert solution.minOperations([5], [1,5,10]) == [4,0,5]

# All elements equal
assert solution.minOperations([7,7,7], [7,5]) == [0,6]

# Query smaller than all elements
assert solution.minOperations([10,20,30], [1]) == [57]

# Query larger than all elements
assert solution.minOperations([1,2,3], [10]) == [24]

# Duplicate values
assert solution.minOperations([2,2,2,2], [1,2,3]) == [4,0,4]

# Mixed values
assert solution.minOperations([1,4,6,8], [3]) == [10]

# Large values
assert solution.minOperations([10**9, 10**9], [1]) == [1999999998]

# Multiple queries
assert solution.minOperations([1,2,3,4,5], [1,3,5]) == [10,6,10]
Test Why
[3,1,6,8], [1,5] Validates standard mixed behavior
[2,9,6,3], [10] Validates query larger than all elements
[5], [1,5,10] Tests single-element arrays
[7,7,7], [7,5] Tests already-equal arrays
[10,20,30], [1] Tests query smaller than all elements
[1,2,3], [10] Tests query larger than all elements
[2,2,2,2], [1,2,3] Tests duplicates
[1,4,6,8], [3] Tests mixed increases and decreases
[10^9,10^9], [1] Tests large-number overflow safety
[1,2,3,4,5], [1,3,5] Tests multiple queries

Edge Cases

Query Smaller Than Every Element

Consider:

nums = [10,20,30]
query = 1

Every value must be decreased. The binary search index becomes 0, meaning the left side is empty.

A common bug is mishandling empty ranges or negative indexing. This implementation handles it naturally because:

leftCount = 0
leftSum = 0

Only the right-side formula contributes to the answer.

Query Larger Than Every Element

Consider:

nums = [1,2,3]
query = 10

Now every value must be increased. The binary search index becomes n.

The implementation correctly handles this because:

rightCount = 0
rightSum = 0

Only the left-side formula contributes.

Arrays With Duplicate Values

Consider:

nums = [2,2,2,2]
query = 2

The answer should be 0.

Using bisect_left correctly places the split before the first occurrence of 2. The formulas still work because elements equal to the query contribute zero cost.

This prevents off-by-one errors that often happen when handling duplicates with binary search.

Very Large Values

The values can reach 10^9, and there may be 10^5 elements.

The total operation count can therefore exceed:

10^14

This is larger than a 32-bit integer can store.

The Go solution uses int64 for all sums and calculations, ensuring no overflow occurs. Python integers automatically expand, so no extra handling is required there.