Problem Description

You are given an integer array nums of size n. Your goal is to make all elements in the array equal using the minimum number of moves.

In each move, you can increment exactly n - 1 elements of the array by 1. This means in each operation, you select one element to keep unchanged while increasing all other elements by 1.

For example, if you have nums = [1, 2, 3]:

• One move could change it to [2, 3, 3] (keeping the last element unchanged)
• Another move could change it to [2, 2, 4] (keeping the first element unchanged)

The problem asks you to find the minimum number of such moves needed to make all array elements equal.

The key insight is that incrementing n - 1 elements by 1 is mathematically equivalent to decrementing one element by 1 relative to all others. So instead of thinking about raising n - 1 elements, you can think about it as bringing all elements down to the minimum value.

The solution uses a mathematical approach: if the minimum value is mi, the sum of all elements is s, and there are n elements, then after k moves:

• The total sum increases by k * (n - 1)
• All elements will equal some final value x
• The minimum element needs k increments to reach x, so x = mi + k

Setting up the equation s + k * (n - 1) = n * x and substituting x = mi + k, we can solve for k:

• s + k * (n - 1) = n * (mi + k)
• s + k * (n - 1) = n * mi + n * k
• k = s - n * mi

Therefore, the minimum number of moves is sum(nums) - min(nums) * len(nums).

Intuition

The key realization is that incrementing n - 1 elements by 1 is equivalent to decrementing 1 element by 1 relative to all others. This perspective shift makes the problem much clearer.

Think about it this way: if we increment all elements except one, we're essentially leaving that one element behind. After many such operations, the element that gets left behind the most will determine our final equal value.

Since we want to minimize the number of moves, we should aim for the smallest possible final value that all elements can reach. The minimum element in the array provides this lower bound - it can never decrease (since we only increment elements), so all elements must eventually reach at least this value.

But wait - the minimum element itself will also be incremented in moves where it's not the one being left behind. After k moves, the minimum element will have been incremented exactly k times (since it's included in the n - 1 elements that get incremented each time). This means the final equal value must be min(nums) + k.

Now we can set up our equation. After k moves:

• Total sum increases by k * (n - 1) (each move adds n - 1 to the total)
• Final sum equals n * (min(nums) + k) (n elements, each with value min(nums) + k)

From sum(nums) + k * (n - 1) = n * (min(nums) + k), we can solve for k:

• sum(nums) + k * n - k = n * min(nums) + n * k
• sum(nums) - k = n * min(nums)
• k = sum(nums) - n * min(nums)

This elegant formula tells us that the minimum moves needed is simply the current sum minus what the sum would be if all elements were already at the minimum value.

Solution Approach

The implementation follows directly from the mathematical derivation. We need to calculate k = sum(nums) - n * min(nums), where:

• sum(nums) is the total sum of all elements in the array
• min(nums) is the minimum value in the array
• n is the length of the array

Let's trace through the mathematical reasoning:

1. Define variables: Let mi be the minimum value, s be the sum of the array, and n be the array length. After k moves, all elements will equal some value x.

2. Set up equations: After k operations:

   • The total sum becomes: s + (n - 1) * k (original sum plus the increments)
   • This must equal: n * x (n elements, each with value x)
   • So: s + (n - 1) * k = n * x

3. Find the relationship: Since the minimum element gets incremented in every move, after k moves it becomes:

   • x = mi + k

4. Substitute and solve: Replace x in our first equation:

   s + (n - 1) * k = n * (mi + k)
   s + (n - 1) * k = n * mi + n * k
   s + n * k - k = n * mi + n * k
   s - k = n * mi
   k = s - n * mi

The Python implementation is remarkably concise:

class Solution:
    def minMoves(self, nums: List[int]) -> int:
        return sum(nums) - min(nums) * len(nums)

This single line computes:

• sum(nums): Gets the total sum s
• min(nums): Finds the minimum value mi
• len(nums): Gets the array length n
• Returns s - mi * n, which is our answer k

The time complexity is O(n) for finding both the sum and minimum in a single pass through the array. The space complexity is O(1) as we only use constant extra space.

Example Walkthrough

Let's walk through a concrete example with nums = [1, 2, 3].

Step 1: Identify what we need

• Sum of array: s = 1 + 2 + 3 = 6
• Minimum value: mi = 1
• Array length: n = 3

Step 2: Apply the formula Using k = s - n * mi:

• k = 6 - 3 * 1 = 6 - 3 = 3

So we need 3 moves to make all elements equal.

Step 3: Verify with actual moves Let's trace through what happens with 3 moves:

Initial state: [1, 2, 3]

Move 1: Keep element at index 2 unchanged, increment others by 1

• [1+1, 2+1, 3] = [2, 3, 3]

Move 2: Keep element at index 2 unchanged, increment others by 1

• [2+1, 3+1, 3] = [3, 4, 3]

Move 3: Keep element at index 1 unchanged, increment others by 1

• [3+1, 4, 3+1] = [4, 4, 4]

All elements are now equal to 4!

Step 4: Validate the math

• Final value x = mi + k = 1 + 3 = 4 ✓
• Total sum after moves: s + (n-1) * k = 6 + 2 * 3 = 12
• Expected sum with all elements at 4: n * x = 3 * 4 = 12 ✓

The formula correctly predicted we need 3 moves, and all elements end up equal to 4, which matches our manual simulation perfectly.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because:

• sum(nums) iterates through all n elements once to calculate the sum, which takes O(n) time
• min(nums) iterates through all n elements once to find the minimum value, which takes O(n) time
• len(nums) returns the length in O(1) time
• The arithmetic operations (subtraction and multiplication) take O(1) time
• Overall: O(n) + O(n) + O(1) + O(1) = O(n)

The space complexity is O(1) as the algorithm only uses a constant amount of extra space regardless of the input size. The sum() and min() functions use internal variables to track the running sum and minimum value respectively, but these are constant space operations that don't scale with input size.

Common Pitfalls

1. Misunderstanding the Problem Statement

Many people initially think they need to track which elements to increment in each move or simulate the actual moves. This leads to overly complex solutions with higher time complexity.

Wrong Approach:

def minMoves(nums):
    moves = 0
    while len(set(nums)) > 1:  # While not all equal
        nums.sort()
        for i in range(len(nums) - 1):
            nums[i] += 1
        moves += 1
    return moves

Why it's wrong: This simulation approach has O(k*n log n) time complexity where k is the number of moves, which can be very large.

Solution: Recognize that incrementing n-1 elements is equivalent to decrementing 1 element relative to others. Focus on the mathematical relationship rather than simulating moves.

2. Integer Overflow in Other Languages

When implementing in languages like Java or C++, the calculation sum(nums) - min(nums) * len(nums) can cause integer overflow for large arrays with large values.

Problematic Code (Java):

public int minMoves(int[] nums) {
    int sum = 0;
    int min = Integer.MAX_VALUE;
    for (int num : nums) {
        sum += num;  // Can overflow!
        min = Math.min(min, num);
    }
    return sum - min * nums.length;
}

Solution: Use long data type or calculate the sum of differences directly:

public int minMoves(int[] nums) {
    int min = Integer.MAX_VALUE;
    for (int num : nums) {
        min = Math.min(min, num);
    }
    int moves = 0;
    for (int num : nums) {
        moves += (num - min);  // Avoids large intermediate sums
    }
    return moves;
}

3. Attempting to Find the Target Value

Some solutions try to determine what the final equal value will be, which adds unnecessary complexity.

Overcomplicated Approach:

def minMoves(nums):
    min_val = min(nums)
    max_val = max(nums)
    # Try to figure out the target value
    target = min_val + (max_val - min_val)  # Wrong!
    # ... complex logic follows

Solution: You don't need to know the final value. The formula sum(nums) - min(nums) * len(nums) directly gives the answer without needing to determine the target.

4. Edge Case Handling

Forgetting to handle edge cases like single-element arrays or arrays where all elements are already equal.

Incomplete Solution:

def minMoves(nums):
    # Missing edge case check
    return sum(nums) - min(nums) * len(nums)

Better Solution:

def minMoves(nums):
    if len(nums) <= 1:
        return 0
    if len(set(nums)) == 1:  # All elements already equal
        return 0
    return sum(nums) - min(nums) * len(nums)

Note: The formula naturally handles these cases (returns 0), but explicit checks can improve code clarity and prevent unnecessary computation.