Minimum Moves to Equal Array Elements II
Problem
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.
nums = [1, 2, 3]2def min_moves2(nums):
nums.sort()
m = nums[len(nums) // 2]
return sum(abs(x - m) for x in nums)function minMoves2(nums) {
nums.sort((a, b) => a - b);
const m = nums[Math.floor(nums.length / 2)];
return nums.reduce((s, x) => s + Math.abs(x - m), 0);
}class Solution {
public int minMoves2(int[] nums) {
Arrays.sort(nums);
int m = nums[nums.length / 2];
int total = 0;
for (int x : nums) total += Math.abs(x - m);
return total;
}
}int minMoves2(vector<int>& nums) {
sort(nums.begin(), nums.end());
int m = nums[nums.size() / 2];
int total = 0;
for (int x : nums) total += abs(x - m);
return total;
}Explanation
We want one target value that all elements move to, with the total number of +1/-1 steps as small as possible. The magic answer is to aim for the median.
Why the median? If the target sits anywhere between the smallest and largest values, every step you shift it left reduces the distance to elements on the left but increases it for elements on the right. The cost is smallest exactly when there are as many elements on one side as the other, which is the middle element.
So the code sorts nums, grabs m = nums[len(nums) // 2] as the median, and then adds up abs(x - m) for every element. That sum is the minimum number of moves.
Example: [1, 2, 3] is already sorted, the median is 2. The moves are |1-2| + |2-2| + |3-2| = 1 + 0 + 1 = 2.
Picking any other target, like 1 or 3, would give 3 moves instead, so the median really is best.