Minimum Moves to Equal Array Elements II — Why the Median Wins [LC 462]

Problem Statement#

Given an integer array nums, in one move you can increment or decrement an element by 1. Return the minimum number of moves to make all elements equal.

Constraints:

• n == nums.length
• 1 <= n <= 10^5
• -10^9 <= nums[i] <= 10^9

Input:  nums = [1,2,3]
Output: 2

Input:  nums = [1,10,2,9]
Output: 16

Why This Problem Matters#

LeetCode 462 is a mathematical reasoning problem asked at Amazon, Meta, and Google. The key insight — that the median minimizes the sum of absolute deviations — is a result from statistics that has direct algorithmic applications. Interviewers use this to test whether candidates can connect mathematical theory to efficient algorithms.

Note the contrast with LC 453 (Minimum Moves to Equal Array Elements I), where each move increments n-1 elements simultaneously. LC 462 allows individual increments and decrements — a completely different problem requiring a different mathematical insight.

The Core Insight#

The median minimizes absolute deviation. The total number of moves equals sum(|nums[i] - target|) for the chosen target. This sum is minimized when target is the median of the array.

Why the median? If you pick any target to the left of the median, moving it right by 1 unit reduces distances to all elements to the right (majority) by more than it increases distances to elements on the left (minority). The median is the exact balance point where no shift can reduce the total further.

Algorithm:

1. Sort the array
2. Find the median (middle element for odd n, or either middle element for even n)
3. Compute sum(|nums[i] - median|)

For even-length arrays, any value between the two medians works equally — picking either middle element gives the same minimum sum.

Visual Dry Run#

nums = [1, 2, 3]

Sorted: [1, 2, 3], median = 2

Moves: |1-2| + |2-2| + |3-2| = 1 + 0 + 1 = 2

Try other targets:

• target=1: 0 + 1 + 2 = 3 (worse)
• target=3: 2 + 1 + 0 = 3 (worse)

nums = [1, 10, 2, 9]

Sorted: [1, 2, 9, 10], medians are 2 and 9. Pick median = 2 (or 9):

• target=2: |1-2|+|2-2|+|9-2|+|10-2| = 1+0+7+8 = 16
• target=9: |1-9|+|2-9|+|9-9|+|10-9| = 8+7+0+1 = 16 — same!

Actually target=5: 4+3+4+5=16. Any value in [2,9] gives 16 — all medians are equivalent.

Solution (Optimal)#

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

var minMoves2 = function(nums) {
    nums.sort((a, b) => a - b);
    const median = nums[Math.floor(nums.length / 2)];
    return nums.reduce((acc, n) => acc + Math.abs(n - median), 0);
};

Time: O(n log n) — dominated by sorting Space: O(1) — no auxiliary data structures

Common Mistakes#

• Using the mean instead of the median — mean minimizes sum of squared deviations, not absolute deviations
• Forgetting to sort before finding the median — median requires the middle element of the sorted array
• Using the average of the two middle elements for even-length arrays — for absolute deviation, any value between the two medians works; pick either one
• Confusing with LC 453 (increment n-1 elements) — that problem's solution uses mean + sum formula, not median
• Integer overflow when computing sums for large arrays with values near 10^9 — use long in Java/C++

Interview Tips#

• State the mathematical claim upfront: "the median minimizes the sum of absolute deviations — standard statistics result"
• Prove it intuitively: "moving the target away from the median increases distance to more elements than it decreases"
• Contrast with LC 453: "when moves affect all elements simultaneously, the mathematics changes entirely"
• If asked for quickselect: median can be found in O(n) average with quickselect — same answer, faster
• Mention the O(n) space approach (use numpy.median in Python) only if the interviewer asks for libraries

Follow-up Questions#

• How do you find the median in O(n) instead of O(n log n)? (Quickselect / nth_element — average O(n), same result)
• What if each move costs differently for increment vs decrement? (Weighted median — more complex optimization)
• Why does mean minimize squared error but median minimizes absolute error? (Calculus: derivative of sum of squares is linear, derivative of sum of absolute values creates a step function — median is where step function crosses zero)
• What if you can only make at most k moves total? (Binary search on the answer or a different DP approach)
• How does this extend to 2D — minimize total Manhattan distance to a single point? (Row median and column median independently — same principle applied per coordinate)

Key Takeaways#

• LeetCode 462 is asked at Amazon, Meta, and Google — mathematical insight problem (median vs mean)
• Median minimizes sum of absolute deviations — this is a classic result from statistics
• Algorithm: sort, pick middle element, compute sum(|nums[i] - median|)
• For even-length arrays, any value between the two middle elements gives the same minimum — pick either
• Time O(n log n) for sorting; O(n) possible with quickselect for the median
• Do NOT use the mean — mean minimizes sum of squared deviations (variance), not absolute deviations
• The contrast with LC 453 (increment n-1 elements, use mean formula) is a common interview trap — know both