Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/462.html

462. Minimum Moves to Equal Array Elements II

Level

Medium

Description

Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1.

You may assume the array’s length is at most 10,000.

Example:

Input:
[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]

Solution

The solution is to make all array elements equal to the median of the array. The median of the array is calculated as follows. If the array’s length is odd, then the middle element is the median. If the array’s length is even, then the average of the two middle elements is the median. In fact, if the array’s length is even, any number between the two middle elements inclusive can be considered as the median, and will lead to the minimum number of moves.

The following is the proof that making all array elements equal to the median of the array costs the minimum number of moves.

Case 1. The length of the array is odd. Suppose the length of the array is 2k + 1, where k is a positive integer (there is no need to consider the case when k = 0, since in this case there is only 1 element and the number of moves needed is 0). In this case, the median is the k-th element in the sorted array. Suppose the median is m. To make all array elements equal to m + 1, the numbers less than or equal to m need one more move and the numbers greater than m need one less move. Since there are at least k + 1 numbers less than or equal to m and there are at most k numbers greater than m, the total number of moves at least increase by 1. To make all array elements equal to m - 1, the numbers greater than than or equal to m need one more move and the numbers less than m need one less move. Since there are at least k + 1 numbers greater than or equal to m and there are at most k numbers less than m, the total number of moves at least increase by 1.

In conclusion, making all array elements equal to a number that is not the median will always cost more moves than making all array elements equal to the median.

Case 2. The length of the array is even. Suppose the length of the array is 2k, where k is a positive integer. In this case, the median is any number between the k-th element and the (k+1)-th element in the sorted array. Suppose the two middle numbers are m and n. To make all array elements equal to m - 1 or n + 1, the total number of moves at least increase by 2, and the reason is similar to case 1.

In conclusion, making all array elements equal to a number that is not the median will always cost more moves than making all array elements equal to the median.

  • class Solution {
    public int minMoves2(int[] nums) {
        Arrays.sort(nums);
        int length = nums.length;
        int median = length % 2 == 0 ? (nums[length / 2 - 1] + nums[length / 2]) / 2 : nums[length / 2];
        int moves = 0;
        for (int num : nums)
            moves += Math.abs(num - median);
        return moves;
    }
}

############

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;
    }
}

  • // OJ: https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/
// 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;
    }
};

  • 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)

############

class Solution(object):
  def minMoves2(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    nums.sort()
    mid = nums[len(nums) / 2]
    return sum(abs(num - mid) for num in nums)


  • func minMoves2(nums []int) int {
	sort.Ints(nums)
	k := nums[len(nums)>>1]
	ans := 0
	for _, v := range nums {
		ans += abs(v - k)
	}
	return ans
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

  • function minMoves2(nums: number[]): number {
    nums.sort((a, b) => a - b);
    const mid = nums[nums.length >> 1];
    return nums.reduce((r, v) => r + Math.abs(v - mid), 0);
}


  • impl Solution {
    pub fn min_moves2(mut nums: Vec<i32>) -> i32 {
        nums.sort();
        let mid = nums[nums.len() / 2];
        let mut res = 0;
        for num in nums.iter() {
            res += (num - mid).abs();
        }
        res
    }
}

All Problems

All Solutions