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
Test cases are designed so that the answer will fit in a 32-bit integer.
Input: nums = [1,2,3]
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]
n == nums.length
1 <= nums.length <= 105
-109 <= nums[i] <= 109
Iterate through range of numbers from lowest to highest number in the array, and find , for which number the moves is minimum
O(range of numbers [low, high]*number of elements in the array)
Based on median
The minimum moves is when we have values of all elements equal to the median in the array. So first calculate median of the array elements , then make all the element to the median values
def minMoves2(self, nums: List[int]) -> int:
median=nums[n//2] if n%2 != 0 else(nums[n//2]+nums[n//2-1])//2
for i in nums:
Two pointer solution
Sort the array first and keep two pointers low and high at the extremes ,and for each of those pair of number find the difference between them , which is the number of moves needed to make those values to the median, repeat this, for next pair of numbers till low<high and sum them all.