Minimum Moves to Equal Array Elements II [Medium] — Median Target
Sanjeev SharmaAdvertisement
Problem Statement
Find the minimum number of moves to make all array elements equal, where each move increments or decrements an element by 1.
Input: [1,2,3] → Output: 2 (make all 2)
Intuition
The optimal target is the median. Sort and sum absolute differences from median.
Solutions
C++
int minMoves2(vector<int>& nums) {
sort(nums.begin(),nums.end());
int mid=nums[nums.size()/2], moves=0;
for(int n:nums) moves+=abs(n-mid);
return moves;
}
Python
def minMoves2(nums: list[int]) -> int:
nums.sort()
median = nums[len(nums) // 2]
return sum(abs(n - median) for n in nums)
JavaScript
var minMoves2 = function(nums) {
nums.sort((a,b)=>a-b);
const mid=nums[Math.floor(nums.length/2)];
return nums.reduce((s,n)=>s+Math.abs(n-mid),0);
};
Complexity
- Time: O(n log n)
- Space: O(1)
Advertisement
