Minimum Moves to Equal Array Elements II

How it works

For absolute-distance cost, moving the target within the middle pair changes left and right costs equally; outside the median range, more values pull the target back toward the middle. Choose a median and sum distances. Python sorts to find it; C++ selects it with nth_element.

Steps

1. Find a median value.
2. Compute the absolute difference from each value to the median.
3. Return the sum.

Complexity

• Time: Python O(n log n); C++ O(n) average with nth_element.
• Space: Python O(n) for median sorting; C++ selection is in place.

Things to watch for

• For even length, any value between the two middle values is optimal.
• C++ selection rearranges the input.
• Use absolute differences, rather than signed sums.

import statistics


class Solution:
  def minMoves2(self, nums: list[int]) -> int:
    median = int(statistics.median(nums))
    return sum(abs(num - median) for num in nums)

class Solution {
 public:
  int minMoves2(vector<int>& nums) {
    const int n = nums.size();
    nth_element(nums.begin(), nums.begin() + n / 2, nums.end());
    const int median = nums[n / 2];
    return accumulate(nums.begin(), nums.end(), 0, [&](int acc, int num) {
      return acc + abs(num - median);
    });
  }
};