Leetcode 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
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 <= 10^5
-10^9 <= nums[i] <= 10^9
Our aim is to make all elements equal with the minimum number of possible moves. If we don’t care about the minimum, then we can just fix 1 element and make all other element equal to this fixed element by doing increment or decrement whatever. But this will not guarantee the minimum and this is not the case we are looking for.
We need to make the array elements equal + we need to do it in the minimum number of moves possible.
First of all, we need to sort the elements and try to make all elements equal to the median element. All the elements from the left needs to be incremented and all the elements from the right needs to be decremented. So if we choose any number other than the median as our fixed number, then the number of moves will be higher. So our idea is simple, just sort the array and take the moves from left and right elements to be equal to the median.
In the problem statement, we are given we can only increment or decrement an element by 1.
So if we consider the right element, ie nums[right], we need
possibleMovesFromRight= nums[right] — nums[middle] to make nums[right] = nums[middle].
If we consider the left element, ie nums[left], we need
possibleMovesFromLeft = nums[middle] — nums[left] to make nums[left] = nums[middle].
So the total amount of moves required will be :
totalMoves = possibleMovesFromRight + possibleMovesFromLeft
= nums[right] — nums[middle] + nums[middle] — nums[left]
= nums[right] — nums[left].
- Sort the given array.
- Take 2 pointers left and right.
- Traverse while left < right.
- Track moves = nums[right] — nums[left].
- Increment left and decrement right.
- Return moves.
Time and Space Complexity
We are sorting the array and traversing through the array after sorting.
So our time complexity will be O(nlogn + n) where n = length of array.
We didn’t make use of any extra space, so space complexity = O(1).