Nerd For Tech
Published in

Nerd For Tech

Photo by Clay Banks on Unsplash

Equal Array Elements — Daily Challenge May

Today’s question is from Daily Leetcode Coding Challenge — May Edition. It is a medium-tagged question. Let us look into the problem statement.

462. Minimum Moves to Equal Array Elements 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.

Example:

Input: nums = [1,2,3]
Output: 2

We can make all number equal to a number. That number can be maximum number of the list or minimum number of that list. It can be also be a median. Upon doing these option we see that the medain number will always give the minimum steps.

Once we decide on the median, we just calculate the sum of absolute difference between the target and current num and get sum of all those difference. This will give the desired mimiumu steps. We are not taking mean as [1, 0, 0, 8, 6] mean will result in 16(2+3+3+5+3) steps while median will take 14(0+1+1+7+5) steps.

Code Implementation:

def minMoves2(nums):
nums.sort()
target = nums[len(nums)//2]
res = 0
for n in nums:
res += abs(target-n)
return res

Complexity Analysis:

  • Time Complexity: O(N*logN) for sorting the array.
  • Space Complexity: O(1)

Happy Coding!!

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Amit Singh Rathore

Amit Singh Rathore

Staff Data Engineer — Writes about Cloud | Big Data | ML