# Minimum Moves to Equal Array Elements II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii)
Canonical: https://scaleengineer.com/dsa/problems/minimum-moves-to-equal-array-elements-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Myntra](https://scaleengineer.com/companies/myntra)
---
## 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 or decrement an element of the array by `1`.

Test cases are designed so that the answer will fit in a **32-bit** integer.

**Example 1:**

**Input:** nums = [1,2,3]
**Output:** 2
**Explanation:**
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

**Example 2:**

**Input:** nums = [1,10,2,9]
**Output:** 16

**Constraints:**

* `n == nums.length`
* `1 <= nums.length <= 105`
* `-109 <= nums[i] <= 109`

# Approaches
## Brute Force by Checking All Possible Targets
This approach considers every possible integer value between the minimum and maximum elements of the array as a potential target to which all elements could be made equal. For each potential target, it calculates the total number of moves required and keeps track of the minimum moves found.
**Time:** O(R * N), where N is the number of elements in `nums` and R is the range `max(nums) - min(nums)`. The outer loop runs R times, and for each iteration, we iterate through all N elements. Given the constraints, R can be up to 2 * 10^9, making this approach infeasible. · **Space:** O(1), as we only use a few variables to store the min/max values and the running sum of moves.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient and will time out for large ranges of input values.; Performs a lot of redundant calculations.
### Explanation
The core idea is that the optimal target value must lie within the range of the array's elements, i.e., between `min(nums)` and `max(nums)`. If we choose a target outside this range, we can always find a better target within the range that requires fewer moves. Therefore, we can iterate through every integer from the minimum value to the maximum value present in the array. For each of these integers, we treat it as the target and calculate the sum of absolute differences from all elements in `nums`. The minimum of these sums is the answer. This method is straightforward but highly inefficient due to the potentially vast range of values between the minimum and maximum elements.
```java
class Solution {
    public int minMoves2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int minVal = Integer.MAX_VALUE;
        int maxVal = Integer.MIN_VALUE;
        for (int num : nums) {
            minVal = Math.min(minVal, num);
            maxVal = Math.max(maxVal, num);
        }
        
        long minMoves = Long.MAX_VALUE;
        
        // This will time out due to large range of minVal to maxVal
        for (long target = minVal; target <= maxVal; target++) {
            long currentMoves = 0;
            for (int num : nums) {
                currentMoves += Math.abs(num - target);
            }
            minMoves = Math.min(minMoves, currentMoves);
        }
        
        return (int) minMoves;
    }
}
```
### Algorithm
- Find the minimum (`minVal`) and maximum (`maxVal`) values in the input array `nums`.
- Initialize a variable `minMoves` to a very large number (e.g., `Long.MAX_VALUE`).
- Loop through each integer `target` from `minVal` to `maxVal`.
- Inside the loop, calculate the `currentMoves` by summing up the absolute differences `|num - target|` for every `num` in `nums`.
- Update `minMoves = Math.min(minMoves, currentMoves)`.
- After the loop finishes, `minMoves` will hold the minimum number of moves.

## Using Sorting to Find the Median
A more efficient approach is based on the mathematical insight that the sum of absolute differences is minimized when the target value is the median of the array. This approach first sorts the array. Instead of explicitly calculating the median, it uses a two-pointer technique on the sorted array to sum the differences between symmetric elements, which is equivalent to summing the absolute differences from the median.
**Time:** O(N log N), where N is the number of elements in the array. The dominant operation is sorting the array. The subsequent two-pointer traversal takes O(N) time. · **Space:** O(log N) to O(N), depending on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitive types uses a variant of Quicksort which requires O(log N) space on average for the recursion stack, but can take O(N) in the worst case.
**Pros:** Much more efficient than the brute-force approach.; Relatively easy to implement using standard library functions.; Guaranteed to find the optimal solution.; The two-pointer implementation is clean and efficient.
**Cons:** The O(N log N) time complexity is not the absolute best possible, as sorting the entire array is more work than is strictly necessary.
### Explanation
The problem of minimizing `sum(|nums[i] - x|)` is a classic one, and the optimal value for `x` is the median of the elements in `nums`. After sorting the array, we can find the median and sum the absolute differences. However, a more elegant calculation is possible. Consider the sorted array. The total moves is `sum(|nums[i] - median|)`. This can be rewritten by pairing the smallest element with the largest, the second smallest with the second largest, and so on. For each pair `(nums[i], nums[n-1-i])`, the number of moves to make them both equal to the median is `(median - nums[i]) + (nums[n-1-i] - median) = nums[n-1-i] - nums[i]`. Summing this over all such pairs gives the total minimum moves. This can be implemented efficiently using two pointers, one starting from the beginning (`i`) and one from the end (`j`) of the sorted array, moving inwards.
```java
import java.util.Arrays;

class Solution {
    public int minMoves2(int[] nums) {
        Arrays.sort(nums);
        long moves = 0;
        int i = 0, j = nums.length - 1;
        while (i < j) {
            moves += nums[j] - nums[i];
            i++;
            j--;
        }
        return (int) moves;
    }
}
```
### Algorithm
- Sort the input array `nums` in non-decreasing order.
- Initialize a variable `moves` to 0.
- Initialize two pointers, `i = 0` and `j = nums.length - 1`.
- While `i < j`:
    - Add the difference `nums[j] - nums[i]` to `moves`.
    - Increment `i` and decrement `j`.
- Return the total `moves`.

## Finding the Median with Quick-select Algorithm
This is the most optimal approach in terms of average-case time complexity. Instead of sorting the entire array to find the median, we can use a selection algorithm like Quick-select to find the median (the k-th smallest element, where k = n/2) in linear time on average. Once the median is found, the total moves are calculated as before.
**Time:** O(N) on average. The Quick-select algorithm has a linear time complexity on average. The recurrence is T(N) = T(N/2) + O(N), which resolves to O(N). In the worst case (due to poor pivot selection), it can degrade to O(N^2). The final summation step is O(N). · **Space:** O(1) for an iterative implementation of Quick-select as shown. A recursive implementation would take O(log N) space on average for the call stack, and O(N) in the worst case.
**Pros:** The most time-efficient approach on average.; Avoids the overhead of a full sort.
**Cons:** More complex to implement correctly compared to the sorting approach.; Has a worst-case time complexity of O(N^2), although this is rare in practice with good pivot strategies.
### Explanation
The Quick-select algorithm is a selection algorithm to find the k-th smallest element in an unordered list. It is related to the Quicksort sorting algorithm. Like Quicksort, it uses a pivot to partition the array into two parts: elements smaller than the pivot and elements larger than the pivot. However, instead of recursing into both sides, it only recurses into the side that contains the k-th element. This reduces the average complexity from O(N log N) to O(N).
The steps are:
1. Find the median element using Quick-select. The median is the element that would be at index `n/2` in a sorted array.
2. Once the median is identified, iterate through the array one more time to sum up the absolute differences from this median.
This avoids the cost of a full sort.
```java
class Solution {
    public int minMoves2(int[] nums) {
        int median = findKthSmallest(nums, nums.length / 2);
        long moves = 0; // Use long to prevent potential overflow
        for (int num : nums) {
            moves += Math.abs(num - median);
        }
        return (int) moves;
    }

    // Helper function to find the (k)-th smallest element (k-th index)
    private int findKthSmallest(int[] nums, int k) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int pivotIndex = partition(nums, left, right);
            if (pivotIndex == k) {
                return nums[pivotIndex];
            } else if (pivotIndex < k) {
                left = pivotIndex + 1;
            } else {
                right = pivotIndex - 1;
            }
        }
        return nums[left];
    }

    private int partition(int[] nums, int left, int right) {
        // A simple pivot selection (last element). Can be improved.
        int pivotValue = nums[right];
        int storeIndex = left;
        for (int i = left; i < right; i++) {
            if (nums[i] < pivotValue) {
                swap(nums, storeIndex, i);
                storeIndex++;
            }
        }
        swap(nums, storeIndex, right);
        return storeIndex;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
```
### Algorithm
- Define a function `quickSelect(nums, k)` to find the k-th smallest element. This function will partition the array and recursively call itself on the correct partition.
- Call `quickSelect(nums, nums.length / 2)` to find the median.
- Once the median is found, calculate the sum of absolute differences: `sum(|num - median|)` for all `num` in `nums`.
- Return the calculated sum.

# Solutions
### Java

```java
class Solution {
public
  int minMoves2(int[] nums) {
    Arrays.sort(nums);
    int k = nums[nums.length >> 1];
    int ans = 0;
    for (int v : nums) {
      ans += Math.abs(v - k);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minMoves2(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    int k = nums[nums.size() >> 1];
    int ans = 0;
    for (int &v : nums)
      ans += abs(v - k);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minMoves2(self, nums: List[int]) -> int: nums . sort() k = nums[len(nums) >> 1] return sum(abs(v - k) for v in nums)

```