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.

For example:

• nums = [1,2,3] should return 3 because [1,2,3] => [2,3,3] => [3,4,3] => [4,4,4] requires 3 moves
• nums = [1,1,1] should return 0 because it already meets the criteria

What is the most efficient way to implement this function? What is the time and space complexity of your solution? Are there any edge cases to consider?

Question

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.length
• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• The answer is guaranteed to fit in a 32-bit integer.

Solution

Naive Approach

The naive approach would be to simulate the moves until all elements are equal. This would involve repeatedly incrementing n - 1 elements and checking if all elements are equal. However, this approach is highly inefficient, especially for large arrays and large differences between elements.

Optimal Approach

The key insight is to realize that incrementing n - 1 elements is equivalent to decrementing one element. So, instead of incrementing n - 1 elements, we can think of decrementing one element in each move. The target value to make all elements equal will be the minimum element in the array. Therefore, the number of moves is the sum of the differences between each element and the minimum element.

Algorithm

1. Find the minimum element in the array.
2. Initialize a variable moves to 0.
3. Iterate through the array, and for each element, add the difference between the element and the minimum element to moves.
4. Return moves.

def min_moves(nums):
    min_num = min(nums)
    moves = 0
    for num in nums:
        moves += num - min_num
    return moves

# Example usage
nums1 = [1, 2, 3]
print(min_moves(nums1))  # Output: 3

nums2 = [1, 1, 1]
print(min_moves(nums2))  # Output: 0

Big(O) Run-time Analysis

The algorithm iterates through the array twice: once to find the minimum element and once to calculate the moves. Both iterations take O(n) time, where n is the length of the array. Therefore, the overall time complexity is O(n).

Big(O) Space Usage Analysis

The algorithm uses only a few constant extra variables (min_num, moves). Therefore, the space complexity is O(1), which is constant.

Edge Cases

1. Empty Array: If the input array is empty, the algorithm should return 0 since there are no elements to make equal. However, based on the constraints, the array will not be empty.
2. Array with One Element: If the array has only one element, the algorithm should return 0 since all elements are already equal.
3. Array with All Elements Equal: If all elements are already equal, the algorithm should return 0 since no moves are needed.
4. Large Numbers: The problem statement mentions that the answer is guaranteed to fit in a 32-bit integer, so we don't need to worry about integer overflow during the summation of moves.

def min_moves_edge_cases(nums):
    if not nums:  # Empty array
        return 0
    
    if len(nums) == 1: # Array with one element
        return 0

    min_num = min(nums)
    moves = 0
    for num in nums:
        moves += num - min_num
    return moves