LeetCode 453 - Minimum Moves to Equal Array Elements

Difficulty: 🟡 Medium
Topics: Array, Math

Solution

Problem Understanding

The problem gives an integer array nums with n elements. In a single move, you are allowed to increment exactly n - 1 elements by 1. Your goal is to determine the minimum number of such moves required to make every element in the array equal.

At first glance, the operation feels unusual because instead of incrementing one element, we increment almost the entire array. However, the key observation is that incrementing n - 1 elements is mathematically equivalent to decrementing the one element that was not incremented.

For example, suppose the array is:

[1, 2, 3]

If we increment the first two elements:

[2, 3, 3]

This has the same relative effect as decreasing the last element from 3 to 2 while leaving the others unchanged.

This transformation is the core insight that simplifies the problem dramatically.

The input constraints are important:

The array length can be as large as 10^5
Values can range from -10^9 to 10^9

Because the input can be large, any solution that repeatedly simulates moves step by step will be too slow. We need a mathematical observation that allows us to compute the answer directly in linear time.

There are several important edge cases to consider:

Arrays where all elements are already equal, the answer should be 0
Arrays containing negative numbers
Arrays with only one element
Arrays with very large values, where overflow could become an issue in some languages
Arrays where the minimum element appears multiple times

The problem guarantees that the final answer fits inside a 32-bit integer, which simplifies implementation details.

Approaches

Brute Force Approach

A direct simulation approach would repeatedly perform moves until all numbers become equal.

One possible strategy is:

Find the current maximum element
Increment every other element by 1
Count the move
Repeat until all elements are equal

This approach is correct because each move follows the problem rules exactly. Eventually, all elements will converge to the same value.

However, this method is extremely inefficient. The number of required moves can be very large, especially when array values differ significantly. Since each move requires scanning the array and updating many elements, the total runtime becomes far too slow for arrays of size 10^5.

Optimal Mathematical Approach

The key insight is that incrementing n - 1 elements is equivalent to decrementing one element.

Instead of thinking about raising all numbers up to the maximum, we can think about reducing all numbers down to the minimum.

Suppose the minimum value in the array is min_value.

Every element larger than min_value must effectively be reduced until it matches the minimum. The number of reductions needed for an element x is:

x - min_value

Therefore, the total number of moves is simply:

sum(nums) - n * min_value

This gives us a linear-time solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k * n)	O(1)	Simulates each move individually, where `k` is the number of moves
Optimal	O(n)	O(1)	Uses mathematical equivalence between incrementing `n - 1` elements and decrementing one element

Algorithm Walkthrough

Optimal Algorithm

Find the minimum element in the array.

This value becomes the target value that all elements will eventually match. Since incrementing n - 1 elements is equivalent to decrementing one element, we can think of the process as reducing all numbers to the minimum. 2. Initialize a variable moves to 0.

This variable will store the total number of moves required. 3. Iterate through every element in the array.

For each element num, compute:

num - min_value

This represents how many effective decrements are needed to bring that number down to the minimum value. 4. Add all these differences together.

The total sum is the minimum number of moves. 5. Return the final result.

Why it works

Each move increases n - 1 elements by 1, which leaves one element unchanged. Relative to the unchanged element, the other elements become larger by 1. This is equivalent to decreasing the unchanged element by 1.

Because of this equivalence, making all elements equal is the same as reducing every element down to the minimum element. The total number of reductions required is exactly the sum of differences between each element and the minimum.

Python Solution

from typing import List

class Solution:
    def minMoves(self, nums: List[int]) -> int:
        minimum_value = min(nums)
        
        moves = 0
        
        for num in nums:
            moves += num - minimum_value
        
        return moves

The implementation starts by finding the minimum value in the array using Python's built-in min() function.

Next, we initialize moves to store the running total of required operations.

We then iterate through every number in the array. For each number, we compute how far it is above the minimum value. That difference represents the number of effective decrements required to make it equal to the minimum.

Finally, we return the accumulated total.

The implementation directly follows the mathematical observation developed earlier, which keeps the code both short and efficient.

Go Solution

func minMoves(nums []int) int {
    minimumValue := nums[0]

    for _, num := range nums {
        if num < minimumValue {
            minimumValue = num
        }
    }

    moves := 0

    for _, num := range nums {
        moves += num - minimumValue
    }

    return moves
}

The Go implementation follows the same logic as the Python version.

Since Go does not provide a built-in min() function for slices, we manually scan the array to find the minimum value.

After that, we perform another pass through the array to accumulate the total difference between each number and the minimum.

Go uses integer types directly, and the problem guarantees that the result fits within a 32-bit integer, so overflow is not a concern here.

Worked Examples

Example 1

Input:

nums = [1, 2, 3]

First, find the minimum value:

minimum_value = 1

Now compute the difference for each element.

Element	Difference from Minimum	Running Moves
1	1 - 1 = 0	0
2	2 - 1 = 1	1
3	3 - 1 = 2	3

Final answer:

This matches the expected result.

Example 2

Input:

nums = [1, 1, 1]

Minimum value:

minimum_value = 1

Now compute differences.

Element	Difference from Minimum	Running Moves
1	0	0
1	0	0
1	0	0

Final answer:

The array is already equal.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to find the minimum, one pass to compute total moves
Space	O(1)	Only a few variables are used

The algorithm performs two linear scans through the array. Since constants are ignored in Big O notation, the total runtime remains O(n).

No additional data structures proportional to the input size are allocated, so the space complexity is constant.

Test Cases

solution = Solution()

assert solution.minMoves([1, 2, 3]) == 3  # Basic example
assert solution.minMoves([1, 1, 1]) == 0  # Already equal
assert solution.minMoves([5]) == 0  # Single element
assert solution.minMoves([1, 2, 4]) == 4  # Different gaps
assert solution.minMoves([0, 0, 0, 0]) == 0  # All zeros
assert solution.minMoves([-1, 0, 1]) == 3  # Negative numbers
assert solution.minMoves([-5, -3, -1]) == 6  # All negative
assert solution.minMoves([1000000000, 1000000000]) == 0  # Large equal values
assert solution.minMoves([1, 1000000000]) == 999999999  # Large range
assert solution.minMoves([3, 3, 4, 5]) == 3  # Multiple minimums

Test Summary

Test	Why
`[1,2,3]`	Standard example from problem statement
`[1,1,1]`	Already equal array
`[5]`	Single element edge case
`[1,2,4]`	Uneven differences
`[0,0,0,0]`	All zeros
`[-1,0,1]`	Includes negative numbers
`[-5,-3,-1]`	Entirely negative values
`[1000000000,1000000000]`	Large equal values
`[1,1000000000]`	Large numerical gap
`[3,3,4,5]`	Multiple occurrences of minimum

Edge Cases

Single Element Array

If the array contains only one element, no moves are needed because all elements are already equal by definition. A naive implementation might accidentally perform unnecessary calculations or assumptions about multiple elements. This implementation handles the case naturally because the difference between the single value and the minimum is zero.

Arrays with Negative Numbers

Negative values can sometimes break incorrect mathematical assumptions. For example:

[-5, -3, -1]

The minimum is -5, and the algorithm correctly computes:

(-5 - -5) + (-3 - -5) + (-1 - -5)
= 0 + 2 + 4
= 6

Because the solution relies only on arithmetic differences, negative values are handled correctly without any special logic.

Arrays Already Equal

When all elements are already identical, every difference from the minimum is zero. The algorithm therefore returns 0.

This is important because simulation-based approaches can accidentally enter unnecessary loops if equality checks are implemented incorrectly.

Very Large Values

The constraints allow values as large as 10^9. Repeated simulation could become extremely slow for such inputs. The mathematical solution avoids this issue entirely by computing the answer directly in linear time.

Additionally, the problem guarantees the final answer fits within a 32-bit integer, so standard integer arithmetic is sufficient in both Python and Go.