Minimum Operations To Make Array Equal - Leetcode Solution

Problem Statement:

Given an array consisting of n integers, find the minimum number of operations required to make all array elements equal. In one operation, we can increment or decrement an element by 1.

Example: Input: [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]

Solution: The brute force solution would be to try all possible ways to make all elements equal by incrementing or decrementing each element one by one in every possible way, and keeping track of the minimum number of steps required. But this approach would be very slow and impractical for large arrays.

A better approach is to observe that in order to make all elements equal, we need to make all elements closer to the median value of the array. If the array has an odd number of elements, the median will be the middle element, and if it has an even number of elements, the median will be the average of the two middle elements.

So the first step is to find the median value of the array. We can do this by sorting the array and then taking the middle element (or the average of two middle elements). Alternatively, we can use the quickselect algorithm to find the kth smallest element (where k is n/2 if n is even, and (n+1)/2 if n is odd).

Once we have the median value, we can calculate the total number of operations required to make all elements equal to the median, by summing up the absolute differences between each element and the median. This can be done in a single pass through the array.

Here is the Python code that implements this approach:

class Solution: def minMoves2(self, nums: List[int]) -> int: nums.sort() median = nums[len(nums)//2] if len(nums)%2 == 1 else (nums[len(nums)//2-1]+nums[len(nums)//2])//2 return sum(abs(num-median) for num in nums)

Time Complexity: O(n log n) due to the sorting step, but can be reduced to O(n) using the quickselect algorithm.

Space Complexity: O(1) since we are using constant extra space to store the median and sum of absolute differences.

1