Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.
In one move, you can increment n - 1 elements of the array by 1.
Example 1:
Input: nums = [1,2,3] Output: 3 Explanation: Only three moves are needed (remember each move increments two elements): [1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
Example 2:
Input: nums = [1,1,1] Output: 0
Constraints:
n == nums.length1 <= nums.length <= 105-109 <= nums[i] <= 109Problem Overview: You’re given an integer array nums. One move lets you increment n − 1 elements by 1. The task is to compute the minimum number of moves required so that all elements become equal.
Approach 1: Brute Force Simulation (O(n * moves) time, O(1) space)
A direct interpretation is to repeatedly increment all elements except the current maximum until every value becomes equal. Each iteration scans the array, finds the maximum element, and increments the remaining n-1 elements. This continues until the array converges to a single value. While this matches the problem statement exactly, the number of operations can grow very large because the gap between elements shrinks slowly. Every move requires a full iteration through the array, making this approach impractical for large inputs.
Approach 2: Mathematical Observation (O(n) time, O(1) space)
The key insight flips the perspective. Incrementing n-1 elements by 1 is equivalent to decrementing a single element by 1. Instead of thinking about raising most numbers, imagine reducing the largest values until all elements match the smallest element in the array. This observation turns the process into a simple counting problem.
If the minimum element in the array is minVal, every other element must be reduced until it equals minVal. The number of required operations for each element is simply nums[i] - minVal. Summing these differences across the entire array gives the total number of moves:
moves = sum(nums) - n * min(nums)
This works because each simulated "decrement" corresponds exactly to one valid operation in the original problem. The algorithm only needs a single pass to compute the array sum and minimum value, making it optimal for large inputs.
This approach relies purely on arithmetic reasoning rather than explicit simulation. You iterate through the array once, track the minimum value, compute the total sum, and apply the formula. No extra data structures are required.
Conceptually, this problem blends math reasoning with simple iteration over an array. Many interview problems follow the same pattern: a naive simulation exists, but a mathematical invariant leads to a much faster solution.
Recommended for interviews: The mathematical observation approach is what interviewers expect. Explaining the equivalence between "increment n−1 elements" and "decrement one element" demonstrates problem‑solving insight. Mentioning the brute force idea first shows you understand the problem mechanics, then deriving the formula shows strong algorithmic reasoning. The optimal solution runs in O(n) time with O(1) extra space.
The problem can be simplified by observing that incrementing n-1 elements is equivalent to decrementing 1 element. Thus, the number of moves required to make all elements in the array equal is equal to the total number of moves required to make all elements equal to the minimum element present in the array.
To achieve this, calculate the difference between each element and the minimum element, summing these differences yields the required number of moves.
This C solution keeps track of the minimum element and computes the sum of differences between each element and the minimum. This sum is the number of moves needed.
Time Complexity: O(n), Space Complexity: O(1)
Let the minimum value of the array nums be mi, the sum of the array be s, and the length of the array be n.
Assume the minimum number of operations is k, and the final value of all elements in the array is x. Then we have:
$
\begin{aligned}
s + (n - 1) times k &= n times x \
x &= mi + k \
\end{aligned}
Substituting the second equation into the first equation, we get:
\begin{aligned}
s + (n - 1) times k &= n times (mi + k) \
s + (n - 1) times k &= n times mi + n times k \
k &= s - n times mi \
\end{aligned}
Therefore, the minimum number of operations is s - n times mi.
The time complexity is O(n), and the space complexity is O(1). Here, n$ is the length of the array.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Mathematical Observation | Time Complexity: O(n), Space Complexity: O(1) |
| Mathematics | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n * moves) | O(1) | Useful for understanding the mechanics of the operation but impractical for large arrays. |
| Mathematical Observation | O(n) | O(1) | Optimal solution for all cases. Uses array sum and minimum value to compute moves directly. |
453. Minimum Moves to Equal Array Elements LeetCode • hakunamatasq • 7,203 views views
Watch 9 more video solutions →Practice Minimum Moves to Equal Array Elements with our built-in code editor and test cases.
Practice on FleetCode