Minimum Moves to Equal Array Elements II: Why the Median Wins

Minimum Moves to Equal Array Elements II is LeetCode 462. Given an integer array nums, you can increment or decrement any element by 1 in a single move. Return the minimum number of moves to make all elements equal.

The problem

You are given an array of integers. In each move, you pick one element and either add 1 or subtract 1. You want every element in the array to end up at the same value, and you want to do it in as few moves as possible.

For example, given nums = [1, 2, 3], the answer is 2. Move 1 up by one and 3 down by one, and everything becomes 2.

Why this problem matters

This problem tests whether you know a fundamental statistical property: the median minimizes the sum of absolute deviations. That property shows up everywhere, from optimization problems to machine learning loss functions. In interviews, recognizing that the optimal target is the median (not the mean) is the difference between a clean O(n log n) solution and a messy simulation that runs out of time.

The key insight

Why the median and not some other value? Here is the intuition. Imagine you have a number line with all your array elements plotted on it. You need to pick a single point, and every element will walk toward that point. Each step costs one move.

If you pick any value to the left of the median, all the elements to the right of the median have to walk further left, while only some elements on the left walk less. Moving the target one step to the right saves one move for every element above the target but costs one move for every element below it. At the median, you have an equal number of elements on each side (or as close to equal as possible), so shifting in either direction cannot reduce the total cost.

This is the property of the median: it is the value that minimizes the sum of absolute differences from all points in the dataset. For an odd-length array, the median is the single middle element. For an even-length array, any value between the two middle elements works, but picking either middle element is simplest.

The code

def minMoves2(self, nums):
    nums.sort()
    median = nums[len(nums) // 2]
    return sum(abs(n - median) for n in nums)

Why this works

The solution has three parts:

1. Sort the array. Sorting lets you find the median by index. After sorting, the median is at position n // 2 (using integer division). For odd-length arrays, this is the exact middle element. For even-length arrays, this is the upper-middle element, which is just as optimal as the lower-middle.

2. Pick the median as the target. The median minimizes the total absolute deviation. No other value produces fewer total moves.

3. Sum absolute differences. For each element, compute how far it is from the median. The total across all elements is the answer.

Visual walkthrough

Let's trace through nums = [1, 10, 2, 9] step by step. This is a four-element example that shows how sorting, finding the median, and summing differences produce the answer.

After sorting we get [1, 2, 9, 10]. The median at index 2 is 9. The total moves: |1-9| + |2-9| + |9-9| + |10-9| = 8 + 7 + 0 + 1 = 16. You could also pick the median at index 1 (value 2) and get 1 + 0 + 7 + 8 = 16. Both middle values produce the same total.

Complexity analysis

Time: O(n log n) because sorting dominates. After sorting, finding the median is O(1) and summing differences is O(n).

Space: O(n) depending on the sorting algorithm. Python's Timsort uses O(n) auxiliary space. If you use an in-place sort, the space drops to O(log n) for the recursion stack.

Note: you could achieve O(n) time using the quickselect algorithm to find the median without fully sorting, but the O(n log n) sorting approach is simpler and more than fast enough for interview purposes.

Building blocks

The median minimizes absolute deviations. This is the core mathematical fact. While the mean minimizes the sum of squared deviations, the median minimizes the sum of absolute deviations. Knowing when to use each statistic is critical for optimization problems. If the cost function is linear (each unit of distance costs the same), the median is your answer.

Sorting to find order statistics. Once the array is sorted, you can read off any order statistic by index. The median, the quartiles, the min, the max: they are all just array lookups after sorting. This pattern shows up in problems that ask for the "k-th smallest" or "middle" value.

Two-pointer equivalence. There is an alternative way to think about the sum of absolute differences. After sorting, you can pair the smallest element with the largest, the second smallest with the second largest, and so on. Each pair contributes nums[n-1-i] - nums[i] to the total. This is equivalent to summing absolute differences from the median, and it avoids needing to identify the median explicitly.

Edge cases

• All elements equal. [5, 5, 5] returns 0. No moves needed since every element is already the same.
• Two elements. [1, 10] returns 9. The median can be either value, and the cost is just the difference between them.
• Single element. [7] returns 0. A single element is trivially "equal."
• Even-length arrays. [1, 2, 9, 10] returns 16 regardless of whether you pick the lower or upper middle value as the target.

From understanding to recall

The entire solution is three lines, but the reasoning behind it is what you need to internalize. Under time pressure, you need to remember: "the median minimizes the sum of absolute deviations." That single fact gives you the target, and the rest is just sorting and summing.

Practice reconstructing the logic from scratch. Start from the question "why the median?" and work forward to the formula. After a few rounds of spaced repetition, the connection between absolute deviations and the median will be automatic. That same insight applies to many optimization problems where you need to pick a central value to minimize total cost.

Related posts

• Minimum Moves to Equal Array Elements - The companion problem (LeetCode 453) where incrementing n-1 elements is equivalent to decrementing one, solved with a different math insight
• Sort Colors - Another problem where sorting order matters, using the Dutch National Flag partitioning technique
• Kth Largest Element in an Array - Finding order statistics efficiently, which connects directly to how we locate the median