LeetCode 462: Minimum Moves to Equal Array Elements II

Problem Restatement

We are given an integer array nums.

In one move, we can either increment or decrement one element by 1.

We need to return the minimum number of moves required to make all array elements equal. The official statement defines the move as incrementing or decrementing one array element by 1.

For example:

nums = [1, 2, 3]

We can make all values equal to 2:

[1, 2, 3] -> [2, 2, 3] -> [2, 2, 2]

The answer is:

2

Input and Output

Function shape:

def minMoves2(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [1, 2, 3]

Choose target value 2.

Moves:

1 -> 2 costs 1 move
2 -> 2 costs 0 moves
3 -> 2 costs 1 move

Total:

1 + 0 + 1 = 2

Answer:

2

Example 2:

nums = [1, 10, 2, 9]

After sorting:

[1, 2, 9, 10]

For an even-length array, any value between the two middle values gives the same minimum. We can choose 2 or 9.

Choose target 2:

abs(1 - 2) = 1
abs(10 - 2) = 8
abs(2 - 2) = 0
abs(9 - 2) = 7

Total:

1 + 8 + 0 + 7 = 16

Answer:

16

Example 3:

nums = [1, 0, 0, 8, 6]

After sorting:

[0, 0, 1, 6, 8]

The median is 1.

Moves:

abs(0 - 1) = 1
abs(0 - 1) = 1
abs(1 - 1) = 0
abs(6 - 1) = 5
abs(8 - 1) = 7

Total:

14

First Thought: Try Every Target Value

A direct idea is to try making all numbers equal to each possible value.

For a target value t, the number of moves is:

sum(abs(num - t) for num in nums)

Then we choose the smallest value.

But the numbers can be very large:

-10^9 <= nums[i] <= 10^9

Trying every possible target value is impossible.

Even trying every value in nums costs:

O(n^2)

because for each candidate target, we scan the whole array.

Problem With Brute Force

The target value determines the cost.

For example:

nums = [1, 2, 9, 10]

If we choose target 1:

0 + 1 + 8 + 9 = 18

If we choose target 2:

1 + 0 + 7 + 8 = 16

If we choose target 9:

8 + 7 + 0 + 1 = 16

If we choose target 10:

9 + 8 + 1 + 0 = 18

The middle values are best.

This points to the median.

Key Insight

The value that minimizes the total absolute distance is the median.

For this problem, the total moves for a target t are:

abs(nums[0] - t) + abs(nums[1] - t) + ... + abs(nums[n - 1] - t)

The median minimizes this sum.

So the algorithm is:

1. Sort the array.
2. Choose the median.
3. Sum distances from every number to the median.

For odd n, there is one median.

For even n, either middle value works.

Why the Median Works

Sort the array:

a[0] <= a[1] <= ... <= a[n - 1]

Pair the smallest and largest values:

a[0], a[n - 1]

For any target t between them, the contribution from this pair is:

abs(a[0] - t) + abs(a[n - 1] - t)

If a[0] <= t <= a[n - 1], this equals:

t - a[0] + a[n - 1] - t = a[n - 1] - a[0]

So any target inside the pair’s interval gives the same pair cost.

If t moves outside that interval, the cost increases.

Now pair the second smallest and second largest:

a[1], a[n - 2]

Again, the target should stay inside that interval.

After pairing all outer elements, the target must lie in the intersection of all these intervals.

That intersection is the median position.

So choosing the median minimizes the total moves.

Algorithm

Sort nums.

Choose:

median = nums[len(nums) // 2]

Then compute:

moves = sum(abs(num - median) for num in nums)

Return moves.

Correctness

After sorting, consider any pair formed by one small value and one large value:

nums[left], nums[right]

For this pair, any target between the two values gives the smallest possible pair cost. Moving the target outside this interval increases the pair cost.

The global target must minimize the sum of all such pair costs.

The median lies inside every paired interval. Therefore, choosing the median minimizes every pair’s contribution at the same time.

Since the total number of moves is the sum of absolute distances from each element to the chosen target, the median gives the minimum possible total.

Thus, the algorithm returns the minimum number of moves.

Complexity

Let n = len(nums).

In Python, sorting may use extra internal memory, so practical auxiliary space can be O(n).

Implementation

class Solution:
    def minMoves2(self, nums: list[int]) -> int:
        nums.sort()
        median = nums[len(nums) // 2]

        moves = 0
        for num in nums:
            moves += abs(num - median)

        return moves

Code Explanation

We sort the input:

nums.sort()

This puts the median at the middle index.

Then:

median = nums[len(nums) // 2]

For odd length, this is the middle value.

For even length, this chooses the right middle value. The left middle value also gives the same minimum.

Then we add the distance from each value to the median:

moves += abs(num - median)

Each unit of distance is one increment or decrement move.

Finally:

return moves

returns the minimum total.

Two-Pointer Implementation

There is another way to compute the same answer after sorting.

Pair smallest with largest, then second smallest with second largest.

For each pair, the required moves are:

nums[right] - nums[left]

Code:

class Solution:
    def minMoves2(self, nums: list[int]) -> int:
        nums.sort()

        left = 0
        right = len(nums) - 1
        moves = 0

        while left < right:
            moves += nums[right] - nums[left]
            left += 1
            right -= 1

        return moves

This works because both values in a pair move toward the median interval.

Testing

def run_tests():
    s = Solution()

    assert s.minMoves2([1, 2, 3]) == 2
    assert s.minMoves2([1, 10, 2, 9]) == 16
    assert s.minMoves2([1, 0, 0, 8, 6]) == 14
    assert s.minMoves2([1]) == 0
    assert s.minMoves2([1, 1, 1]) == 0
    assert s.minMoves2([-1, 0, 1]) == 2
    assert s.minMoves2([-10, -5, 0, 5, 10]) == 30

    print("all tests passed")

run_tests()

Test meaning: