Skip to main content

462 - Minimum Moves to Equal Array Elements II

Difficulty: Medium | Pattern: Math (Median) | Company tags: Amazon, Google, Facebook

Problem Statement​

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.

Example 1:

Input: nums = [1,2,3]
Output: 2  (make all 2: 1→2 (1 move), 3→2 (1 move))

Example 2:

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

Algorithm Flow​

Approach: Sort + Median — O(n log n)​

Key insight: The optimal target value is the median. Moving all elements to the median minimizes the total absolute deviation.

def minMoves2(nums: list[int]) -> int:
    nums.sort()
    median = nums[len(nums) // 2]
    return sum(abs(x - median) for x in nums)

Why Median?​

For any target t, total cost = sum |nums[i] - t|. This is minimized when t is the median. If t is below the median, we can reduce cost by moving it up. Above the median, moving down reduces cost. The median is the "balance point."

Alternative: Two Pointers — No Sorting by Absolute Position​

def minMoves2(nums: list[int]) -> int:
    nums.sort()
    result = 0
    left, right = 0, len(nums) - 1
    while left < right:
        result += nums[right] - nums[left]
        left += 1
        right -= 1
    return result

The two-pointer approach pairs min and max elements — their distance is the cost to equalize them regardless of target.

Dry Run​

nums = [1,2,3]

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

Sum: |1-2| + |2-2| + |3-2| = 1 + 0 + 1 = 2 ✓

nums = [1,10,2,9] → sorted [1,2,9,10], median = 9

Sum: |1-9|+|2-9|+|9-9|+|10-9| = 8+7+0+1 = 16 ✓

Complexity​

  • Time: O(n log n) for sort
  • Space: O(1)

Key Terms​

TermDefinition
MedianThe middle value of a sorted array; minimizes sum of absolute deviations.
Absolute deviationThe distance `
Two pointersTechnique pairing elements from opposite ends of a sorted array.
Convex cost functionA cost function (like sum of absolute differences) with a single global minimum, here at the median.

FAQ​

Q: Why does the median minimize total moves instead of the mean? A: The cost function sum |x_i - t| is piecewise linear and minimized at the median, not the mean (which minimizes squared error). Moving t away from the median in either direction increases the count of elements on the far side more than it decreases on the near side.

Q: Does it matter which median we pick when n is even? A: No — any value between the two middle elements gives the same minimum sum, so picking either middle element (as nums[n//2]) works.

Q: Can this be solved without sorting? A: Yes, using a selection algorithm (quickselect) to find the median in O(n) average time, though the two-pointer variant still needs the array sorted to pair min/max correctly.

Q: What if the array has duplicate elements? A: No issue — duplicates just contribute 0 cost if they equal the median, and the logic is unaffected.

Q: How does this differ from LeetCode 462's sibling problem (Minimum Moves to Equal Array Elements I)? A: Variant I only allows incrementing n-1 elements by 1 each move, which is equivalent to raising all but one element — the answer there is sum(nums) - n * min(nums), a different formula entirely.

Quick Revision​

  • Goal: minimize total moves to make all elements equal via +1/-1 per move.
  • Optimal target is the median of the array.
  • Sort the array, then sum |nums[i] - median|.
  • Alternative: two-pointer pairing of smallest and largest elements accumulates the same total.
  • Time complexity dominated by sort: O(n log n); space O(1) extra.
  • Mean does not work here — only median minimizes sum of absolute differences.
  • Works identically for even and odd length arrays.
  • Classic pattern also seen in "meeting point" and "minimize total distance" problems.
  • Minimum Moves to Equal Array Elements I — variant using +1 on n-1 elements (formula-based, not median-based).
  • 300 - Longest Increasing Subsequence — different pattern, but also relies on sorted-order reasoning.
  • Best Meeting Point (median-of-medians on a grid) — same core idea of minimizing sum of absolute distances via the median.