Solution: Minimum Moves to Equal Array Elements II
Tags: algorithms, javascript, java, python
Published: 2021-05-19 10:12:19

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/discuss/1217591).*

---

#### [Leetcode Problem #462 (*Medium*): Minimum Moves to Equal Array Elements II](https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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`.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:|nums = [1,2,3]
Output:|2
Explanation:|Only two moves are needed (remember each move increments or decrements one element):<br>[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 <= 10^5`
 - `-10^9 <= nums[i] <= 10^9`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

This problem is deceptive in its simplicity. Ultimately, the value to which you want to set each element equal is the **median** of the sorted **nums** array. To come to this realization, we have to first think about the nature of the problem.

Let's consider a possible scenario in which we've decided that our target value is **x** which would take **ans** number of moves to complete. What would happen to **ans** if we increased **x** by **1**? If we did, each element that is below the new **x** would have to spend another move to get up to **x**, but every element that is above the new **x** would have to spend one less move to get down to **x**.

This means that **x** should naturally move up if there are more elements above **x** than below. It also means the inverse, that **x** should move down if there are more elements below **x** than above. The natural outcome of this is that **x** will settle at a spot where there are the same number of elements on either side, which is the median value of **nums**.

To find the median value, we'll have to first sort **nums**. If **nums** has an even number of elements, any value between the two middle elements, inclusive, will work for calculating the answer, so we don't have to worry about which of the two elements we use for our solution.

After we have the median value, we can just iterate through **nums** and find the sum of the differences of each number from the median value, which should be our answer.

 - _**Time Complexity: O(N * log N)** where **N** is the length of **nums**, for sorting **nums**_
 - _**Space Complexity: O(1)**_

---

#### ***Implementation:***

For C++, we can use **nth_element** to find the **median** in **O(N) time** without having to fully sort **nums**.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var minMoves2 = function(nums) {
    nums.sort((a,b) => a - b)
    let ans = 0, median = nums[~~(nums.length / 2)]
    for (let i = 0; i < nums.length; i++) ans += Math.abs(median - nums[i])
    return ans
}
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        nums.sort()
        ans, median = 0, nums[len(nums) // 2]
        for num in nums: ans += abs(median - num)
        return ans
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int minMoves2(int[] nums) {
        Arrays.sort(nums);
        int ans = 0, median = nums[nums.length / 2];
        for (int num : nums) ans += Math.abs(median - num);
        return ans;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int minMoves2(vector<int>& nums) {
        vector<int>::iterator mid = nums.begin() + nums.size() / 2;
        nth_element(nums.begin(), mid, nums.end());
        int ans = 0, median = nums[nums.size() / 2];
        for (auto num : nums) ans += abs(median - num);
        return ans;
    }
};
```