#462

Medium

LeetCode Problem Workspace

Minimum Moves to Equal Array Elements II

Find the minimum moves to equalize all array elements using increments or decrements with array and math techniques.

Problem Statement

You are given an integer array nums of length n. In one move, you can increment or decrement any single element by 1. Determine the minimum total number of moves required to make all elements equal, ensuring the solution fits in a 32-bit integer.

The array may contain both positive and negative integers, and its length can be up to 105. Your goal is to compute the smallest number of unit moves across all elements to equalize the array, using array sorting and mathematical reasoning to optimize the operation count.

Examples

Example 1

Input: nums = [1,2,3]

Output: 2

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

Example details omitted.

Constraints

n == nums.length
1 <= nums.length <= 105
-109 <= nums[i] <= 109

Solution Approach

Sort the Array

Begin by sorting the array to make median-based calculations straightforward. Sorting organizes elements so that moving numbers toward the median minimizes cumulative distance.

Select the Median

Choose the middle element after sorting as the median. Using the median as the target ensures the sum of absolute differences, representing moves, is minimized according to the Array plus Math pattern.

Sum Absolute Differences

Iterate through the array and calculate the absolute difference between each element and the median. The total sum of these differences gives the minimum moves needed to equalize all elements.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) due to sorting, and space complexity is O(1) if sorting is in-place. Computing differences afterward is linear in n.

What Interviewers Usually Probe

Mentions array length up to 105 and presence of negative numbers.
Hints at using a central value to minimize total moves.
Tests understanding of absolute differences and sorting.

Common Pitfalls or Variants

Common pitfalls

Targeting mean instead of median, which can increase move count.
Ignoring negative numbers when calculating differences.
Failing to sort first, making median selection ambiguous.

Follow-up variants

Compute minimum moves if only increment operations are allowed.
Find minimum moves when array elements must reach a value divisible by k.
Determine minimum moves to equal elements when allowed moves are +/- d instead of 1.

FAQ

Why is the median used instead of the mean in this problem?

Using the median minimizes the sum of absolute differences, which directly reduces the total number of moves required.

Can the solution handle negative numbers in the array?

Yes, the median approach works for both positive and negative integers since it calculates absolute differences.

What is the time complexity of this solution?

Sorting dominates the time complexity at O(n log n), while summing absolute differences is O(n).

Does the array length affect the choice of median?

For even-length arrays, any element between the two middle elements can serve as the median without changing the minimal move total.

How does GhostInterview help with Minimum Moves to Equal Array Elements II?

It provides direct guidance on sorting, median selection, and calculating absolute differences to find the minimal move count efficiently.

terminal

Solution

Solution 1: Sorting + Median

This problem can be abstracted to finding a point on a number line such that the sum of distances from $n$ points to this point is minimized. The answer is the median of the $n$ points.

1

2

3

4

5

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)

Continue Practicing

#539 minimum time difference #368 largest divisible subset #628 maximum product of three numbers