453. Minimum Moves to Equal Array Elements

Minimum Moves to Equal Array Elements - LeetCode

The key idea is to look at how each move changes the differences between the numbers.

Intuition

We want to make every element equal. In one move, we can increase exactly n - 1 elements by 1.

Simulating those moves would mean repeatedly choosing which element to leave unchanged. But there is a simpler way to think about the operation.

Increasing every element except one has the same relative effect as decreasing that one element by 1.

For example, starting with [1, 2, 3], increasing the first two elements gives [2, 3, 3]. If we then subtract 1 from every element, we get [1, 2, 2].

Subtracting the same amount from every element does not change whether they are equal. So, for counting moves, we can treat each operation as decreasing one element instead.

In this version of the problem, the best target is the smallest number already in the array:

  • we cannot reach a larger target using only decreases
  • choosing a smaller target would require extra moves for every element

That means each number needs num - min_num moves. Adding those differences gives the minimum total.

For [1, 2, 3], the minimum is 1:

(1 - 1) + (2 - 1) + (3 - 1) = 0 + 1 + 2 = 3

The original operations would make the array equal at [4, 4, 4]. The minimum value is our target in the equivalent decreasing version, not the final value in the original array.

Implementation

I use:

  • min_num to store the smallest value in nums
  • a list comprehension to calculate each number's difference from min_num
  • sum() to add those differences together

If every element is already equal, all the differences are 0, so the result is also 0.

# 453. Minimum Moves to Equal Array Elements

def minMoves(nums):
    min_num = min(nums)

    return sum([num - min_num for num in nums])


print(minMoves([1, 2, 3]))  # 3

Complexity

  • Time: O(n). Finding the minimum, building the list of differences, and summing it each take linear time.
  • Space: O(n). The list comprehension creates a temporary list containing one difference per element.

Using sum(num - min_num for num in nums) would avoid creating that list and reduce the extra space to O(1).