LeetCode 453: Minimum Moves to Equal Array Elements

Problem Restatement

We are given an integer array nums.

In one move, we can increment exactly n - 1 elements by 1, where n is the length of the array.

That means each move leaves one element unchanged and increases every other element.

We need to return the minimum number of moves required to make all elements equal. The official statement defines this move as incrementing n - 1 elements by 1.

For example:

nums = [1, 2, 3]

One possible sequence is:

[1, 2, 3]
[2, 3, 3]
[3, 4, 3]
[4, 4, 4]

So the answer is:

3

Input and Output

Function shape:

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

Examples

Example 1:

nums = [1, 2, 3]

The answer is:

3

Explanation:

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

Example 2:

nums = [1, 1, 1]

All elements are already equal.

The answer is:

0

Example 3:

nums = [5, 6, 8]

The minimum element is 5.

The differences from the minimum are:

5 - 5 = 0
6 - 5 = 1
8 - 5 = 3

The answer is:

0 + 1 + 3 = 4

First Thought: Simulate the Moves

A direct idea is to repeatedly increment all elements except the current largest element.

For example:

nums = [1, 2, 3]

The largest element is 3, so increment the other two:

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

Then the largest element is still one of the 3s, so increment the other two:

[2, 3, 3] -> [3, 4, 3]

Then:

[3, 4, 3] -> [4, 4, 4]

This gives the right answer for small arrays, but simulation is a poor solution.

Problem With Simulation

The number of moves can be large.

For example:

nums = [1, 1000000000]

Each move increments only one of the two elements.

The answer is:

999999999

Simulating nearly one billion moves is too slow.

We need a formula.

Key Insight

Incrementing n - 1 elements by 1 has the same relative effect as decrementing the one untouched element by 1.

For equality, only the differences between numbers matter.

Consider:

[1, 2, 3]

If we increment the first two elements:

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

Relative to subtracting 1 from every element, this is equivalent to:

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

The largest element effectively moved down by 1.

So instead of thinking:

“Increment n - 1 elements.”

Think:

“Decrement one element.”

To make all elements equal with the fewest moves, we reduce every element down to the minimum element.

So the answer is the sum of differences from the minimum.

Formula

Let:

mn = min(nums)

Every number num needs:

num - mn

effective decrements to reach mn.

So the total number of moves is:

sum(num - mn for num in nums)

This is the same as:

sum(nums) - len(nums) * min(nums)

Algorithm

Find the minimum value in the array:

mn = min(nums)

Initialize moves = 0.

For each number num in nums, add its difference from the minimum:

moves += num - mn

Return moves.

Correctness

Each move increments n - 1 elements and leaves one element unchanged.

Compared to all elements moving together, this is equivalent to decreasing the unchanged element by 1.

Therefore, the problem becomes equivalent to reducing selected elements by 1 until all elements become equal.

The smallest element is the lowest value all elements can be reduced to without needing to reduce it below its original value.

For any element num, it must be effectively reduced by exactly:

num - min(nums)

to reach the minimum value.

Summing this over all elements gives the total number of required effective decrements.

Each effective decrement corresponds to one original move.

Therefore, the algorithm returns the minimum number of moves.

Complexity

Let n = len(nums).

Implementation

class Solution:
    def minMoves(self, nums: list[int]) -> int:
        mn = min(nums)
        moves = 0

        for num in nums:
            moves += num - mn

        return moves

A shorter version:

class Solution:
    def minMoves(self, nums: list[int]) -> int:
        return sum(nums) - len(nums) * min(nums)

Code Explanation

We first find the smallest element:

mn = min(nums)

Then we count how far every element is above that minimum:

for num in nums:
    moves += num - mn

If a number already equals mn, it contributes 0.

If a number is larger than mn, it contributes the number of effective decrements needed to bring it down to mn.

Finally:

return moves

returns the minimum number of moves.

Testing

def run_tests():
    s = Solution()

    assert s.minMoves([1, 2, 3]) == 3
    assert s.minMoves([1, 1, 1]) == 0
    assert s.minMoves([5, 6, 8]) == 4
    assert s.minMoves([1, 1000000000]) == 999999999
    assert s.minMoves([-1, 0, 1]) == 3
    assert s.minMoves([10]) == 0

    print("all tests passed")

run_tests()

Test meaning: