462

462. Minimum Moves to Equal Array Elements II (Medium)

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

Related Topics:
Array, Math, Sorting

Similar Questions:

• Best Meeting Point (Hard)
• Minimum Moves to Equal Array Elements (Medium)
• Minimum Operations to Make a Uni-Value Grid (Medium)
• Removing Minimum Number of Magic Beans (Medium)

Solution 1.

Sort the array.

For A[i], the numbers to its right need right - (N - i - 1) * A[i] steps where right = A[i+1] + A[i+2] + .. + A[N-1]; the numbers to its left need i * A[i] - left steps. So in total we need right - (N - i - 1) * A[i] + i * A[i] - left moves.

We can keep track of left and right on the fly, and get the minimum moves.

// OJ: https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int minMoves2(vector<int>& A) {
        long left = 0, right = 0, N = A.size(), ans = LONG_MAX;
        sort(begin(A), end(A));
        for (int n : A) right += n;
        for (long i = 0; i < N; ++i) {
            right -= A[i];
            long moves = right - (N - i - 1) * A[i] + i * A[i] - left;
            ans = min(ans, moves);
            left += A[i];
        }
        return ans;
    }
};

Solution 2. Median

Any Median minimizes the sum of absolute deviations. See more

// OJ: https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
// https://discuss.leetcode.com/topic/68736/java-just-like-meeting-point-problem
class Solution {
public:
    int minMoves2(vector<int>& A) {
        sort(begin(A), end(A));
        int i = 0, j = A.size() - 1, ans = 0;
        while (i < j) ans += A[j--] - A[i++];
        return ans;
    }
};

Solution 3. Median

If the array has odd number of elements, there is only a single median which minimizes the sum of absolute deviations.

If the array has even number of elements, any numbers between (including) the two median numbers minimizes the sum of absolute deviations.

// OJ: https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/
// Author: github.com/lzl124631x
// Time: O(N) on average, O(N^2) in the worst case
// Space: O(1)
class Solution {
public:
    int minMoves2(vector<int>& A) {
        int N = A.size();
        nth_element(begin(A), begin(A) + N / 2, end(A));
        int median = A[N / 2], ans = 0;
        for (int n : A) ans += abs(n - median);
        return ans;
    }
};