{x}
blog image

Minimum Moves to Equal Array Elements II

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

462. Minimum Moves to Equal Array Elements II

Problem Description

Given an integer array nums of size n, find 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.

Solution: Sorting and Median

The optimal solution involves finding the median of the array. The median minimizes the sum of absolute differences between each element and a chosen target value.

Intuition:

Imagine the numbers on a number line. The point that minimizes the total distance to all other points is the median. Moving all elements towards the median minimizes the total moves needed.

Algorithm:

  1. Sort the array: Sort the input array nums in ascending order. This step allows easy identification of the median.
  2. Find the median: The median is the middle element if the array length is odd, or the average of the two middle elements if the array length is even.
  3. Calculate total moves: For each element in the sorted array, calculate the absolute difference between the element and the median. Sum up these differences to get the total number of moves.

Time Complexity: O(n log n), dominated by the sorting step.

Space Complexity: O(log n) or O(n) depending on the sorting algorithm used (in-place sorting like merge sort uses O(log n) space, while others might use O(n)).

Code Implementation

Python:

class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        nums.sort()
        median = nums[len(nums) // 2]  # Integer division for median
        moves = sum(abs(x - median) for x in nums)
        return moves

Java:

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

C++:

#include <algorithm>
#include <vector>
#include <cmath>
 
class Solution {
public:
    int minMoves2(std::vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        int median = nums[nums.size() / 2];
        int moves = 0;
        for (int num : nums) {
            moves += std::abs(num - median);
        }
        return moves;
    }
};

Go:

import (
	"sort"
	"math"
)
 
func minMoves2(nums []int) int {
	sort.Ints(nums)
	median := nums[len(nums)/2]
	moves := 0
	for _, num := range nums {
		moves += int(math.Abs(float64(num - median)))
	}
	return moves
}

JavaScript:

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves2 = function(nums) {
    nums.sort((a,b)=> a-b);
    const median = nums[Math.floor(nums.length / 2)];
    let moves = 0;
    for(let num of nums){
        moves += Math.abs(num - median);
    }
    return moves;
};

TypeScript:

function minMoves2(nums: number[]): number {
    nums.sort((a, b) => a - b);
    const median = nums[Math.floor(nums.length / 2)];
    let moves = 0;
    for (const num of nums) {
        moves += Math.abs(num - median);
    }
    return moves;
}

Rust:

use std::cmp::abs;
 
impl Solution {
    pub fn min_moves2(mut nums: Vec<i32>) -> i32 {
        nums.sort();
        let median = nums[nums.len() / 2];
        nums.iter().map(|&x| abs(x - median)).sum()
    }
}

All the code examples above follow the same algorithm and achieve the same result. They differ only in syntax and specific library functions used for sorting and absolute value calculation.