2602. Minimum Operations to Make All Array Elements Equal LeetCode Solution

In this guide, you will get 2602. Minimum Operations to Make All Array Elements Equal LeetCode Solution with the best time and space complexity. The solution to Minimum Operations to Make All Array Elements Equal problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Operations to Make All Array Elements Equal solution in C++
Minimum Operations to Make All Array Elements Equal solution in Java
Minimum Operations to Make All Array Elements Equal solution in Python
Additional Resources

2602. Minimum Operations to Make All Array Elements Equal LeetCode Solution image

Problem Statement of Minimum Operations to Make All Array Elements Equal

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:

Increase or decrease an element of the array 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].
Note that after each query the array is reset to its original state.

Example 1:

Input: nums = [3,1,6,8], queries = [1,5]
Output: [14,10]
Explanation: 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]
Explanation: 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

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(n)

2602. Minimum Operations to Make All Array Elements Equal LeetCode Solution in C++

class Solution {
 public:
  vector<long long> minOperations(vector<int>& nums, vector<int>& queries) {
    const int n = nums.size();
    vector<long long> ans;
    vector<long long> prefix{0};

    ranges::sort(nums);

    for (int i = 0; i < n; ++i)
      prefix.push_back(prefix.back() + nums[i]);

    for (const long query : queries) {
      const int i = ranges::upper_bound(nums, query) - nums.begin();
      // Since nums[0..i) <= query, nums[i..n) > `query`, we should
      // - increase each num in nums[0..i) to `query` and
      // - decrease each num in nums[i..n) to `query`.
      const long inc = query * i - prefix[i];
      const long dec = prefix[n] - prefix[i] - query * (n - i);
      ans.push_back(inc + dec);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

2602. Minimum Operations to Make All Array Elements Equal LeetCode Solution in Java

class Solution {
  public List<Long> minOperations(int[] nums, int[] queries) {
    final int n = nums.length;
    List<Long> ans = new ArrayList<>();
    long[] prefix = new long[n + 1];

    Arrays.sort(nums);

    for (int i = 0; i < n; ++i)
      prefix[i + 1] = prefix[i] + nums[i];

    for (final int query : queries) {
      int i = Arrays.binarySearch(nums, query);
      if (i < 0)
        i = -i - 1;

      // Since nums[0..i) <= query, nums[i..n) > `query`, we should
      // - increase each num in nums[0..i) to `query` and
      // - decrease each num in nums[i..n) to `query`.
      final long inc = (long) query * i - prefix[i];
      final long dec = prefix[n] - prefix[i] - (long) query * (n - i);
      ans.add(inc + dec);
    }

    return ans;
  }
}
// code provided by PROGIEZ

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

class Solution:
  def minOperations(self, nums: list[int], queries: list[int]) -> list[int]:
    n = len(nums)
    nums.sort()
    prefix = list(itertools.accumulate(nums, initial=0))
    splits = [(query, bisect.bisect_right(nums, query)) for query in queries]
    return [(query * i - prefix[i]) +
            (prefix[-1] - prefix[i] - query * (n - i))
            for query, i in splits]
 # code by PROGIEZ