Minimum Cost To Make Array Equal - Leetcode Solution

Problem Statement:

Given an array of integers arr of length n, you need to make all the elements of the array equal to some integer value with the minimum possible cost.

The cost of changing an element is the absolute difference between the current element and the new element.

Return the minimum cost to make all elements equal.

Example 1:

Input: arr = [1,2,3] Output: 2 Explanation: We can pick 2, which is the middle element. So the cost to change the array to [2,2,2] is abs(1-2)+abs(2-2)+abs(3-2)=2.

Example 2:

Input: arr = [4,3,1] Output: 4 Explanation: We can pick 3, which is the middle element. So the cost to change the array to [3,3,3] is abs(4-3)+abs(3-3)+abs(1-3)=4.

Solution:

The minimum cost to make all the elements in the array equal can be calculated by finding the median of the array and then calculating the sum of absolute differences of all the elements of the array with the median.

We will first sort the array in non-decreasing order. Then we will find the median of the array. If the length n of the array is odd, then the median will be the value at the index (n-1)/2. If the length n of the array is even, then the median will be the average of the values at the indices n/2-1 and n/2.

Once we have the median value, we will calculate the sum of absolute differences of all the elements of the array with the median. This can be done by iterating over the array and adding the absolute difference between each element and the median to a running sum.

The resulting sum will be the minimum cost to make all the elements in the array equal.

Pseudo-code:

sort the array arr in non-decreasing order if length of arr is odd median = arr[(length of arr-1)/2] else median = (arr[length of arr/2-1] + arr[length of arr/2])/2 initialize a variable sum to 0 for each element x in arr add abs(median - x) to sum return sum

Time Complexity:

The time complexity of the above solution is O(n log n) due to the sorting operation. The space complexity is O(1) as we are not using any extra space other than the input array.

1