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] <= 109In #453 Minimum Moves to Equal Array Elements, each move increases n-1 elements by 1. At first glance this suggests repeatedly adjusting most of the array, but a key mathematical insight simplifies the problem. Instead of thinking about increasing many elements, you can view the operation as effectively decreasing a single element relative to the others.
This perspective reveals that the optimal strategy is to make every element equal to the smallest value in the array. The total number of moves depends on how far each element is from this minimum value. By scanning the array once to compute the minimum and tracking the total difference between elements and that minimum, we can determine the required number of moves.
This approach avoids simulation and works in linear time. It only requires a single pass through the array and a few variables for aggregation, resulting in O(n) time complexity and O(1) additional space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Math-based single pass using array minimum | O(n) | O(1) |
Code with Alisha
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.
Time Complexity: O(n), Space Complexity: O(1)
1def min_moves(nums):
2 min_element = min(nums)
3 return sum(num - min_element for num in nums)
4
5nums = The Python solution leverages Python's built-in functions to determine the minimum and accumulate the differences succinctly.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The smallest element represents the baseline that other elements must align with when considering the equivalent 'decrement' perspective. By measuring how much larger each element is than this minimum, we can determine how many operations are needed.
Yes, variations of this problem appear in coding interviews at large tech companies. Interviewers often use it to test whether candidates can recognize mathematical transformations that simplify seemingly iterative problems.
No complex data structure is required for this problem. A simple array traversal with variables to track the minimum value and cumulative differences is sufficient to compute the answer efficiently.
The optimal approach uses a mathematical observation: incrementing n-1 elements is equivalent to decrementing one element. This means the problem reduces to making all elements equal to the smallest value in the array and counting the total differences.