Minimum Moves to Equal Array Elements III - Solution & Explanation

Problem 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.