Watch 5 video solutions for Minimum Moves to Equal Array Elements III, a easy level problem involving Array, Math. This walkthrough by Programming Live with Larry has 966 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums.
In one move, you may increase the value of any single element nums[i] by 1.
Return the minimum total number of moves required so that all elements in nums become equal.
Example 1:
Input: nums = [2,1,3]
Output: 3
Explanation:
To make all elements equal:
nums[0] = 2 by 1 to make it 3.nums[1] = 1 by 1 to make it 2.nums[1] = 2 by 1 to make it 3.Now, all elements of nums are equal to 3. The minimum total moves is 3.
Example 2:
Input: nums = [4,4,5]
Output: 2
Explanation:
To make all elements equal:
nums[0] = 4 by 1 to make it 5.nums[1] = 4 by 1 to make it 5.Now, all elements of nums are equal to 5. The minimum total moves is 2.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 100Problem Overview: You are given an integer array and can increment any element by 1 in a single move. The goal is to compute the minimum number of moves required so every value in the array becomes equal.
Approach 1: Try Every Possible Target Value (Brute Force) (Time: O(n * R), Space: O(1))
A straightforward idea is to try making every element equal to a candidate target value and count the moves needed. For each candidate target t, iterate through the array and sum t - nums[i] for elements smaller than t. The smallest total across all candidates is the answer. This works because each move increases an element by exactly one. The downside is efficiency. If the candidate range R is large (for example from the minimum to maximum value), the algorithm repeatedly scans the array and becomes unnecessarily slow.
Approach 2: Calculate Sum and Maximum Value (Optimal) (Time: O(n), Space: O(1))
The key observation is that when you can only increment elements, the final equal value must be at least the current maximum element. Choosing any value larger than the maximum would only add extra moves without benefit. Therefore, the optimal target is exactly the maximum value in the array.
Once you know the target, the number of moves required for each element is simply the difference between the maximum and that element. Summing these differences across the array gives the total moves. Instead of computing each difference separately, use a compact formula: moves = maxValue * n - sum(nums). One pass through the array gives both the total sum and the maximum value.
This approach relies on simple arithmetic and a single iteration over the array. No additional data structures are required. Problems like this commonly appear in interview questions involving array traversal and basic math reasoning.
Recommended for interviews: Interviewers expect the mathematical insight that the target value must be the maximum element. A brute force attempt shows understanding of the problem mechanics, but recognizing the max * n - sum relationship demonstrates strong problem‑solving and optimization skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Try Every Target Value (Brute Force) | O(n * R) | O(1) | Useful for understanding the mechanics of increment operations and verifying correctness on small ranges |
| Calculate Sum and Maximum Value | O(n) | O(1) | Optimal approach for large arrays; single pass using simple arithmetic |