#2602

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Minimum Operations to Make All Array Elements Equal

Find the minimum number of operations to make all elements in an array equal for each query.

Problem Statement

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: choose any element and either increase or decrease it 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]. For each query, elements larger than the query value should be decreased, and elements smaller should be increased to match the target value.

Examples

Example 1

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

Output: [14,10]

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]

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

Solution Approach

Binary Search for Efficient Search Space Reduction

The key to solving this problem efficiently is using binary search over the valid answer space. We compute the cost to adjust all elements in nums to each query[i] and find the optimal answer in logarithmic time.

Prefix Sum Optimization

By using prefix sums, we can quickly calculate the cost of transforming elements to any queried value by summing the differences in a precomputed fashion, further reducing the complexity of the solution.

Array Sorting

Sorting the array beforehand allows us to perform the binary search more effectively by ensuring that we can easily partition the array based on the target query values.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity for this problem depends on the sorting step (O(n log n)) and the binary search over the array for each query (O(log n) for each query). Thus, the overall time complexity can range from O(n log n) to O(n log n + m log n), depending on the final approach.

What Interviewers Usually Probe

The candidate should demonstrate knowledge of binary search in a numerical setting and how it applies to optimizing the number of operations.
Look for a solid understanding of prefix sums and sorting as methods to efficiently calculate the number of operations for each query.
A strong candidate will discuss handling large input sizes and how the algorithm scales, particularly when dealing with up to 10^5 elements.

Common Pitfalls or Variants

Common pitfalls

Failing to consider the complexity of performing operations over large arrays and queries, which can lead to inefficient solutions.
Not utilizing binary search or prefix sums to optimize the search space and computation, leading to a time complexity that's too high.
Overcomplicating the solution by not recognizing the simplicity of binary search combined with sorted arrays for answering each query.

Follow-up variants

Consider variations where you might need to handle queries with negative integers or zero, requiring additional handling.
What if we need to handle arrays where elements can be changed by a fixed increment or decrement?
You might want to explore what happens when all elements are already equal in the array before performing any operations.

FAQ

How do I approach the 'Minimum Operations to Make All Array Elements Equal' problem?

Use binary search over the valid answer space to efficiently determine the minimum number of operations for each query.

Why should I sort the array for this problem?

Sorting the array ensures that binary search can be applied efficiently, allowing us to partition the array and calculate the number of operations more quickly.

What is the complexity of solving the 'Minimum Operations to Make All Array Elements Equal' problem?

The time complexity is dominated by O(n log n) for sorting the array, followed by O(log n) operations for each query, resulting in O(n log n + m log n) overall.

What is the optimal approach for calculating the number of operations for each query?

Using a combination of binary search, sorting, and prefix sums allows for efficient computation of the number of operations for each query.

How can GhostInterview help me prepare for this problem?

GhostInterview provides practice with binary search and array manipulation, helping you optimize your solution while ensuring it scales to large input sizes.

terminal

Solution

Solution 1: sort + prefix sum + binary search

First, we sort the array $nums$ and calculate the prefix sum array $s$ with a length of $n+1$, where $s[i]$ represents the sum of the first $i$ elements in the array $nums$.

1

2

3

4

5

6

7

8

9

10

11

12

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

Continue Practicing

#2448 minimum cost to make array equal #2389 longest subsequence with limited sum #2271 maximum white tiles covered by a carpet