# Minimum Moves to Equal Array Elements
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-moves-to-equal-array-elements)
Canonical: https://scaleengineer.com/dsa/problems/minimum-moves-to-equal-array-elements
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
**Companies:** [Indeed](https://scaleengineer.com/companies/indeed), [Coursera](https://scaleengineer.com/companies/coursera)
---
## Problem
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 <= 105`
* `-109 <= nums[i] <= 109`
* The answer is guaranteed to fit in a **32-bit** integer.

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem. We repeatedly find the largest element and increment all other `n-1` elements by 1. We keep a count of these operations, called 'moves'. The simulation stops when all elements in the array become equal, and we return the total count of moves.
**Time:** O(m * n), where `n` is the length of the array and `m` is the total number of moves. Each move requires O(n) time to find the maximum element and update the others. Since `m` can be very large (up to the order of 10^9), this approach is not feasible. · **Space:** O(1), as we modify the array in-place and use only a constant amount of extra space for variables.
**Pros:** It is straightforward to understand as it directly models the problem statement.
**Cons:** Extremely inefficient due to its high time complexity.; It will result in a 'Time Limit Exceeded' error for most competitive programming platforms on medium to large inputs.
### Explanation
The brute-force method involves a loop that continues as long as the array's elements are not all identical. In each iteration of this loop, we perform one 'move'. A move consists of finding the largest value in the array and then incrementing all other `n-1` elements. A counter tracks the number of moves. The process is guaranteed to terminate because the difference between the maximum and minimum elements decreases or stays the same in each step, but the values themselves increase, eventually converging. However, the number of moves can be very large, making this simulation too slow for the given constraints.

```java
public class Solution {
    public int minMoves(int[] nums) {
        int moves = 0;
        int n = nums.length;
        if (n <= 1) {
            return 0;
        }

        while (true) {
            int min = nums[0];
            int max = nums[0];
            int max_idx = 0;

            for (int i = 1; i < n; i++) {
                if (nums[i] < min) {
                    min = nums[i];
                }
                if (nums[i] > max) {
                    max = nums[i];
                    max_idx = i;
                }
            }

            if (min == max) {
                break;
            }

            for (int i = 0; i < n; i++) {
                if (i != max_idx) {
                    nums[i]++;
                }
            }
            moves++;
        }
        return moves;
    }
}
```
### Algorithm
- Initialize a `moves` counter to 0.
- Start an infinite loop.
- Inside the loop, check if all elements in the array are equal. A simple way is to find the minimum and maximum elements; if they are the same, all elements are equal.
- If they are equal, break the loop and return `moves`.
- If not, find the index of the maximum element.
- Iterate through the array and increment every element by 1, except for the maximum element.
- Increment the `moves` counter.

## Using Sorting
A crucial observation is that incrementing `n-1` elements by 1 has the same effect on the relative differences between elements as decrementing a single element by 1. To make all elements equal, we must bring them all to a common value. To minimize the number of moves (or decrements), the target value must be the minimum element of the original array. Therefore, the problem reduces to calculating the sum of differences between each element and the minimum element. This approach first sorts the array to easily identify the minimum element.
**Time:** O(n log n), dominated by the sorting step. The subsequent loop to sum the differences takes O(n) time. · **Space:** O(log n) to O(n), depending on the sorting algorithm's implementation. For instance, Java's `Arrays.sort` for primitives uses a variant of Quicksort, which has an average space complexity of O(log n) for the recursion stack.
**Pros:** Significantly more efficient than the brute-force simulation.; Based on a correct mathematical insight that simplifies the problem.
**Cons:** The time complexity is dominated by sorting, which is not the most optimal way to find the minimum element.
### Explanation
By rephrasing the problem, we can find a more efficient solution. Instead of incrementing `n-1` elements, we can think of it as decrementing one element. The goal is to make all elements equal. The most efficient way to do this by decrementing is to make all elements equal to the initial minimum value. The total number of moves is the sum of `nums[i] - min_val` for all elements `nums[i]`.

This approach first sorts the array, which places the minimum element at the first index (`nums[0]`). Then, it iterates through the rest of the array, summing up the differences between each element and this minimum value.

```java
import java.util.Arrays;

public class Solution {
    public int minMoves(int[] nums) {
        Arrays.sort(nums);
        int moves = 0;
        for (int i = 1; i < nums.length; i++) {
            moves += nums[i] - nums[0];
        }
        return moves;
    }
}
```
### Algorithm
- Sort the input array `nums` in ascending order.
- The first element, `nums[0]`, is now the minimum element in the array.
- Initialize a variable `moves` to 0.
- Iterate through the array from the second element (`i = 1`) to the end.
- For each element `nums[i]`, calculate the difference `nums[i] - nums[0]` and add it to `moves`.
- After the loop, `moves` will hold the total number of moves required. Return `moves`.

## Mathematical Approach with Single Pass
This is the most optimal approach. It uses the same mathematical insight as the sorting approach: the total number of moves is `sum(nums) - n * min_val`. However, it recognizes that sorting is an unnecessary step. Both the sum of the array and its minimum element can be found in a single pass, leading to a linear time solution.
**Time:** O(n), because we iterate through the array only once to find the sum and the minimum element. · **Space:** O(1), as it only requires a few variables to store the sum and the minimum value, independent of the input size.
**Pros:** Optimal time complexity of O(n).; Optimal space complexity of O(1).; Simple to implement once the mathematical formula is known.
**Cons:** The underlying mathematical trick might not be immediately obvious to everyone.
### Explanation
This approach is based on the formula `moves = sum(nums) - n * min_val`. To calculate this, we need two values: the sum of all elements and the minimum element in the array. Both of these can be computed efficiently by iterating through the array just once. We maintain a running sum and simultaneously track the minimum value seen so far. After a single pass, we have both values and can compute the result directly. This avoids the O(n log n) cost of sorting.

```java
public class Solution {
    public int minMoves(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        
        long sum = 0;
        int min_val = Integer.MAX_VALUE;
        
        for (int num : nums) {
            sum += num;
            min_val = Math.min(min_val, num);
        }
        
        return (int)(sum - (long)nums.length * min_val);
    }
}
```
Using `long` for the sum and during the calculation is a safe practice to prevent intermediate overflow, especially since element values can be large, even though the final answer is guaranteed to fit in a 32-bit integer.
### Algorithm
- Initialize `min_val` to `Integer.MAX_VALUE` and `sum` to 0 (using a `long` type for sum to prevent overflow).
- Iterate through the array `nums` once.
- In each iteration, add the current element to `sum`.
- Also, update `min_val` if the current element is smaller than the current `min_val`.
- After the loop, you will have the sum of all elements and the minimum element.
- The result is `sum - (n * min_val)`, where `n` is the length of the array. Cast the final result back to `int` as the answer is guaranteed to fit.

# Solutions
### Java

```java
class Solution { public int minMoves ( int [] nums ) { return Arrays . stream ( nums ). sum () - Arrays . stream ( nums ). min (). getAsInt () * nums . length ; } }
```

### CPP

```cpp
class Solution { public: int minMoves ( vector < int >& nums ) { int s = 0 ; int mi = 1 << 30 ; for ( int x : nums ) { s += x ; mi = min ( mi , x ); } return s - mi * nums . size (); } };
```

### Python

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