Difficulty: Medium Link: Day 19:May Leetcode Challenge
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
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]
Input: nums = [1,10,2,9] Output: 16
n == nums.length
1 <= nums.length <= 105
-109 <= nums[i] <= 109
One brute force approach can be to consider every element as the pivot and count the number of aways to make other elements equal to the pivot. We can track the minimum of those moves and this would be our answer. We would need two nested loops for checking every combination of numbers with the pivot, so it would be a solution bounded by O(N2). Can we do something better?
If we arrange the values in ascending order and plot it on a histogram, we can notice that moves needed is the absolute difference between the peaks. If the moves cover the mid-way, then the total moves would be minimum. The values on the left of mid value are lesser and all values on the right are greater. This middle value has a special name in the statistics ,called the “median”. This is the middle values in the sorted list.
We can easily find the median by sorting the array and finding the middle value. Then we can find the sum of absolute difference with the median in a single iteration.
Time = O(NLogN)
Space = O(1)