453. Minimum Moves to Equal Array Elements

  • Array
  • Math
TIME
O(n)
SPACE
O(1)
problem on leetcode ↗source on github ↗

Intuition

Adding 1 to every element except one changes the differences between elements exactly as subtracting 1 from that one element would. Only the differences matter for "all equal", so each move is really "decrease one element by 1". The cheapest target is then the minimum, since nothing can go below it without wasting moves, and every element x needs x - min moves to get there.

Approach

  1. Find min(nums).
  2. Return sum(x - min for x in nums), which equals sum(nums) - n * min(nums).

Complexity

  • Time: O(n)
  • Space: O(1)

Edge Cases

  • One element or all equal: 0 moves
  • Negative values: only the differences matter, so the formula is unchanged
  • sum(nums) alone can reach 10^14 and n * min can be just as large, so Java sums the differences x - min in a long; the final answer fits in an int by the problem's guarantee

Code

class Solution:
    def minMoves(self, nums: list[int]) -> int:
        """
        453. Minimum Moves to Equal Array Elements
        Time: O(n)
        Space: O(1)
        """
        # Raising n - 1 elements by 1 is the same, relative to each other, as
        # lowering the remaining one by 1. So bring every element down to the min.
        return sum(nums) - len(nums) * min(nums)