462. Minimum Moves to Equal Array Elements II

Problem statement

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.

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 <= 10^5.

• -10^9 <= nums[i] <= 10^9.

Solution 1: Median - The math behind the problem

You are asked to move all elements of an array to the same value M. The problem can be reduced to identifying what M is.

First, moving elements of an unsorted array and moving a sorted one are the same. So you can assume nums is sorted in some order. Let us say it is sorted in ascending order.

Second, M must be in between the minimum element and the maximum one. Apparently!

We will prove that M will be the median of nums, which is nums[n/2] of the sorted nums.

In other words, we will prove that if you choose M a value different from nums[n/2], then the number of moves will be increased.

In fact, if you choose M = nums[n/2] + x, where x > 0, then:

• Each element nums[i] that is less than M needs more x moves, while each nums[j] that is greater than M can reduce x moves.

• But the number of nums[i] is bigger than the number of nums[j].

• So the total number of moves is bigger.

The same arguments apply for x < 0.

Example 3

For nums = [0,1,2,2,10]. Its median is 2. The minimum number of moves is 2 + 1 + 0 + 0 + 8 = 11.

If you choose M = 3 (the average value, the mean), the total number of moves is 3 + 2 + 1 + 1 + 7 = 14.

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minMoves2(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    const int median = nums[nums.size() / 2];
    int moves = 0;
    for (int& a: nums) {
        moves += abs(a - median);
    }
    return moves;
}
int main() {
    vector<int> nums{1,2,3};
    cout << minMoves2(nums) << endl;
    nums = {1,10,2,9};
    cout << minMoves2(nums) << endl;
}

Output:
2
16

Complexity

• Runtime: O(nlogn), where n = nums.length.

• Extra space: O(1).

Solution 2: Using std::nth_element to compute the median

What you only need in Solution 1 is the median value. Computing the total number of moves in the for loop does not require the array nums to be fully sorted.

In this case, you can use std::nth_element to reduce the runtime complexity.

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minMoves2(vector<int>& nums) {
    const int mid = nums.size() / 2;    
    std::nth_element(nums.begin(), nums.begin() + mid, nums.end());
    const int median = nums[mid];
    int moves = 0;
    for (int& a: nums) {
        moves += abs(a - median);
    }
    return moves;
}
int main() {
    vector<int> nums{1,2,3};
    cout << minMoves2(nums) << endl;
    nums = {1,10,2,9};
    cout << minMoves2(nums) << endl;
}

Output:
2
16

Complexity

• Runtime: O(n), where n = nums.length.

• Extra space: O(1).

Modern C++ notes

In the code of Solution 2, the partial sorting algorithm std::nth_element will make sure for all indices i and j that satisfy 0 <= i <= mid <= j < nums.length,

nums[i] <= nums[mid] <= nums[j].

With this property, if mid = nums.length / 2, then the value of nums[mid] is unchanged no matter how nums is sorted or not.

---

What is your approach? The problem was picked from leetcode.com. You can submit your solution in any programming language and check the performance.

Thanks for reading. Feel free to share your thought about my content and check out my FREE book 10 Classic Coding Challenges.