Minimum Operations To Make Array Equal Ii - Leetcode Solution

Problem Statement: Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.

In one move, you can increment or decrement an element of the array by 1.

Example: Input: nums = [1,2,3] Output: 2

Explanation: Only two moves are needed (remember each move increments or decrements one element): [1,2,3] => [2,2,3] => [2,2,2]

Approach: The key fact which can be used to solve this problem is that the median of a sorted array is the optimal position to make all the elements in the array equal. The reason behind this is that, any element which is greater than the median of the array needs to be at least decremented by one, whereas any element which is smaller than the median of the array needs to be at least incremented by one.

Thus, the first step involved in solving the problem is to sort the array. Once the array is sorted, we can compute the median of the array which is given by the following formula:

median = (nums[(n-1)/2] + nums[n/2])/2;

The next step involves computing the number of operations required to make all the elements of the array equal to the median value. This can be done by iterating through all the elements of the array and computing the absolute difference between each element and the median of the array.

The output of the function will be the sum of the pairwise differences computed in the previous step. We need to ensure that we add the pairwise differences in this step, as the problem states that we can increase or decrease an element by only one unit in one operation. Thus, we need to perform separate operations to increase/decrease an element by more than one unit.

Code:

class Solution { public: int minMoves2(vector<int>& nums) { std::sort(nums.begin(), nums.end()); int median = (nums[(nums.size()-1)/2] + nums[nums.size()/2])/2; int res = 0; for(auto& num : nums) { res += std::abs(num - median);
} return res; } };

Time Complexity: The time complexity of the solution is O(nlogn), as we need to sort the array. The cost of computing the median of the array is O(1). Finally, we need to iterate over the array once to compute the minimum number of moves required to make all the elements in the array equal. Thus, the overall time complexity of the solution is O(nlogn).

Space Complexity: The space complexity of the solution is O(1), as we need to store only a few variables like the median of the array, and the minimum number of moves required to make all the elements in the array equal. Thus, the overall space complexity of the solution is O(1).

1