Watch 10 video solutions for Minimum Moves to Equal Array Elements, a medium level problem involving Array, Math. This walkthrough by hakunamatasq has 7,203 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |