# 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:

```python
nums = [1, 2, 3]
```

We can make all values equal to `2`:

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

The answer is:

```python
2
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | Minimum number of moves |
| Move | Increment or decrement one element by `1` |
| Goal | Make every element equal |

Function shape:

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

## Examples

Example 1:

```python
nums = [1, 2, 3]
```

Choose target value `2`.

Moves:

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

Total:

```python
1 + 0 + 1 = 2
```

Answer:

```python
2
```

Example 2:

```python
nums = [1, 10, 2, 9]
```

After sorting:

```python
[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`:

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

Total:

```python
1 + 8 + 0 + 7 = 16
```

Answer:

```python
16
```

Example 3:

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

After sorting:

```python
[0, 0, 1, 6, 8]
```

The median is `1`.

Moves:

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

Total:

```python
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:

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

Then we choose the smallest value.

But the numbers can be very large:

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

Trying every possible target value is impossible.

Even trying every value in `nums` costs:

```python
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:

```python
nums = [1, 2, 9, 10]
```

If we choose target `1`:

```python
0 + 1 + 8 + 9 = 18
```

If we choose target `2`:

```python
1 + 0 + 7 + 8 = 16
```

If we choose target `9`:

```python
8 + 7 + 0 + 1 = 16
```

If we choose target `10`:

```python
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:

```python
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:

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

Pair the smallest and largest values:

```python
a[0], a[n - 1]
```

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

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

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

```python
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:

```python
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:

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

Then compute:

```python
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:

```python
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)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | Sorting dominates the runtime |
| Space | `O(1)` extra | The scan uses only a few variables |

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

## Implementation

```python
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:

```python
nums.sort()
```

This puts the median at the middle index.

Then:

```python
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:

```python
moves += abs(num - median)
```

Each unit of distance is one increment or decrement move.

Finally:

```python
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:

```python
nums[right] - nums[left]
```

Code:

```python
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

```python
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:

| Test | Why |
|---|---|
| `[1,2,3]` | Standard example |
| `[1,10,2,9]` | Even-length array |
| `[1,0,0,8,6]` | Unsorted odd-length array |
| `[1]` | Single element |
| `[1,1,1]` | Already equal |
| `[-1,0,1]` | Negative and positive values |
| `[-10,-5,0,5,10]` | Symmetric values around median |