Minimum Moves to Equal Array Elements

Problem Statement

In this problem, we are given an array of integers named nums of size n. Our task is to determine the minimum number of operations needed to make all the elements of the array equal. Each operation allows us to increment n-1 elements of the array by 1. This unique constraint means that in each operation, almost all elements (except one) are increased. Understanding and efficiently handling the operation to balance inequalities in the array is central to solving this problem.

Examples

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 <= 105
• -109 <= nums[i] <= 109
• The answer is guaranteed to fit in a 32-bit integer.

Approach and Intuition

Understanding the Problem with Examples:

1. Example 1:

   • Input: nums = [1,2,3]
   • Output: 3
   • Explanation: Each operation allows incrementing two of the three elements once. Thus:
     • From [1,2,3] to [2,3,3] - the first and second elements are incremented.
     • From [2,3,3] to [3,4,3] - the first and third elements are incremented.
     • From [3,4,3] to [4,4,4] - the second and third elements are incremented, bringing all elements to an equal value after three operations.

2. Example 2:

   • Input: nums = [1,1,1]
   • Output: 0
   • Explanation: In this straightforward case, all elements are already equal, and hence, no operations are needed.

Deducing Threads from Constraints and Examples:

• Since n == nums.length and nums can have a maximum length of 105, the solution needs to scale efficiently up to this limit.
• The values of nums[i] can be both negative and positive but are constrained by 32-bit integers, meaning that arithmetic operations won't surpass the integer limits provided in typical programming environments.
• Given the nature of the problem, where each operation applies a +1 to every element except one, it becomes apparent that aiming to level up lower elements to match the higher ones in fewer operations could be an approach. We can think of each operation as reducing the relative difference between the maximum and the non-maximal elements.

Conceptual Breakdown:

• Optimal Approach: Instead of actually performing the operations, it's more optimal to calculate the necessary steps based on problem constraints:
  • Calculate the minimum value, minVal, in the array.
  • Compute the sum of differences between each element in the array and minVal. This difference indicates the total number of increments needed for each element to reach the minimum value if we were moving in reverse - decrementing the largest value each time instead of augmenting all others.

This insight switches the problem from a potentially brutish mechanical simulation to a swift arithmetic calculation, optimizing the process and ensuring it fits within allowed computational constraints.

Solutions

public class Solution {
    public int minimumOperations(int[] arr) {
        int operations = 0, minimum = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            minimum = Math.min(minimum, arr[i]);
        }
        for (int j = 0; j < arr.length; j++) {
            operations += arr[j] - minimum;
        }
        return operations;
    }
}