Minimum moves to make array elements equal ii

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 1.

Test cases are designed so that the answer will fit in a 32-bit integer.

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

Constraints:

  • n == nums.length
  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109

Approach 1:

Iterate through range of numbers from lowest to highest number in the array, and find , for which number the moves is minimum

Time:

O(range of numbers [low, high]*number of elements in the array)

=O(n²) approx

Space :O(1)

Approach2:

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:
nums.sort()
n=len(nums)
if n==0:
return 0
else:
res=0
median=nums[n//2] if n%2 != 0 else(nums[n//2]+nums[n//2-1])//2
for i in nums:
res+=abs(i-median)
return res

Time :O(nlgn)

Space :O(1)

Approach 3:

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.

low=0
high=len(nums)-1
while(low<high):

Time: O(nlogn)

Space: O(1)

Tech-Enthusiast, Coder,Explorer,Geeky,Computer Science Engineering|A piece of code delivers everything that you need.