Minimum Moves To Equal Array Elements Ii - Leetcode Solution

Problem Statement:

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

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

Example 1:

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]

Example 2:

Input: nums = [1,10,2,9] Output: 16

Solution:

Approach:

The minimum moves to equalize array elements can be achieved by calculating the median of the unsorted array. The beauty of picking the median is that it is one of the few numbers, which could result in the minimum number of moves required to equalize all the array elements.

Steps:

1. Sort the input array.
2. Find the median of the array. If the array length is even, the median is the average of the two middle elements.
3. The minimum number of moves required is equal to the sum of the deviations of each element from the median.

Algorithm:

1. Sort the input array.
2. Initialize variables to keep track of the array length and median element.
3. Find the median element. If the length of the array is even, find the average of the middle two elements.
4. Initialize a variable to keep track of the sum of deviations from the median.
5. Iterate over each element of the sorted array:
   • Get the absolute difference between the current element and the median.
   • Add it to the sum of deviations.
6. Return the sum of deviations.

Pseudo Code:

1. Sort the input array.
2. Initialize n=length of array.
3. If n is even, median=average of array[n/2-1] and array[n/2]. Else, median=array[n/2].
4. Initialize deviation=0.
5. Iterate over each element of the array:
   • deviation += |array[i]-median|.
6. Return deviation.

Code Implementation:

class Solution {
public:
    int minMoves2(vector<int>& nums) {
        int n=nums.size();
        sort(nums.begin(),nums.end());
        int median=0;
        if(n%2==0)
        {
            median=(nums[n/2-1]+nums[n/2])/2;
        }
        else
        {
            median=nums[n/2];
        }
        int deviation=0;
        for(int i=0;i<n;i++)
        {
            deviation+=abs(nums[i]-median);
        }
        return deviation;
    }
};

Time Complexity:

Sorting the array using the inbuilt sort method takes O(nlogn) time complexity. Finding the median and calculating the deviation takes O(n) time complexity. Therefore, the total time complexity of the algorithm is O(nlogn).

Space Complexity:

The algorithm uses only constant extra space, so the space complexity is O(1).

Conclusion:

Therefore, the problem has been solved by calculating the median of the unsorted array and iterating over each element to get the sum of deviations from the median.

1