3736. Minimum Moves to Equal Array Elements III
- Array
- Math
TIME
O(n)
SPACE
O(1)
Intuition
Moves only increase values, so no element can come down to meet the others. The common target has to be at least max(nums), and every step above it costs n extra moves. So the target is the max, and each element x needs max - x moves.
Approach
- Find
max(nums)andsum(nums). - Return
n * max - sum.
Complexity
- Time: O(n)
- Space: O(1)
Edge Cases
- One element or all equal: 0 moves
- Only the max differs from the rest (
[1,1,5]): every other element climbs to it - Constraints are tiny (
n, nums[i] <= 100), so no overflow concerns
Code
from typing import List
class Solution:
def minMoves(self, nums: List[int]) -> int:
"""
3736. Minimum Moves to Equal Array Elements III
Time: O(n)
Space: O(1)
"""
# Values only go up, so everything rises to the current max.
return len(nums) * max(nums) - sum(nums)/**
* 3736. Minimum Moves to Equal Array Elements III
* Time: O(n)
* Space: O(1)
*/
class Solution {
public int minMoves(int[] nums) {
int max = 0, sum = 0;
for (int x : nums) {
max = Math.max(max, x);
sum += x;
}
// Values only go up, so everything rises to the current max.
return nums.length * max - sum;
}
}