Minimum Operations to Make All Array Elements Equal — LeetCode 2602 Python Solution

The problem

You are given an array nums consisting of positive integers. You are also given an integer array queries of size m.

Example

Input

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

Output

[14,10]

Explanation

For the first query we can do the following operations:

Python solution

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

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 2602. Minimum Operations to Make All Array Elements Equal is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems