Domain 2MediumCORE

Minimum Moves to Equal Array Elements II

We are given a non-empty array of integers nums. The goal is to make all elements equal using the minimum number of moves, where one move consists of incrementing or decrementing any single element by 1.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Math

462. Minimum Moves to Equal Array Elements II

Model: qwen3.5:9b
Topics: Math
FAANG asked: 0
Acceptance rate: 54.4%


Problem Breakdown

We are given a non-empty array of integers nums. The goal is to make all elements equal using the minimum number of moves, where one move consists of incrementing or decrementing any single element by 1.

Inputs: A list of integers (can include negatives). Output: An integer representing the total count of operations required. Constraints/Edge Cases:

  • Array length is at most 10,000 (N≤104N \le 10^4), suggesting an O(N)O(N) or O(Nlog⁡N)O(N \log N) solution is expected; O(N2)O(N^2) will likely TLE (Time Limit Exceeded).
  • The target value to which all elements converge does not necessarily have to be one of the original numbers, though mathematically we can prove it should ideally be near the middle.
  • Negative values are allowed and handled naturally by absolute difference logic.

Intuition

Initially, a brute-force approach might suggest trying every possible integer as a target value (from min(nums) to max(nums)) and calculating the cost for each. This is O((M−N)2)O((M-N)^2) or worse depending on range size, which is inefficient given constraints.

The key insight comes from recognizing this as an optimization problem involving absolute differences: ∑∣nums[i]−target∣\sum |nums[i] - target|. In 1D space, minimizing the sum of distances to a point is solved by finding the median.

  • If we pick a target smaller than the median, moving it up reduces distance for more elements on the right side than those on the left.
  • Conversely, picking a target larger than the median increases total cost. Thus, the optimal convergence point lies at the middle element(s) of the sorted array.

Approach

  1. Sort the input array to easily access the central value. Sorting takes O(Nlog⁡N)O(N \log N) time.
  2. Identify the median. For an odd-length array, it is nums[len // 2]. For an even-length array, any integer between the two middle elements minimizes cost; picking one of them (e.g., index len // 2) works perfectly for integers because the cost function is flat in that range.
  3. Calculate the total moves by summing the absolute difference between every element and this median value: ∑∣nums[i]−median∣\sum |nums[i] - \text{median}|.

Complexity Analysis

  • Time: O(Nlog⁡N)O(N \log N) due to sorting. The summation loop is O(N)O(N). Overall dominated by sort.
  • Space: O(1)O(1) auxiliary space if we ignore the stack usage of the sorting algorithm (Python’s Timsort uses O(N)O(N) in worst case for stability, but generally considered efficient).

Solution

def minMoves2(nums):
    # Sort to find the median element easily
    nums.sort()
    
    n = len(nums)
    # The optimal target value is the median. 
    # For even N, any integer between the two middle elements works; 
    # picking one of them (index n // 2) yields minimal cost for integers.
    median = nums[n // 2]
    
    moves = sum(abs(num - median) for num in nums)
    
    return moves

Edge Cases Handled

  • Single Element: Loop runs once, abs(x-x) is 0; returns correct result (0).
  • All Elements Equal: Median equals all elements; absolute differences are all 0.
  • Negative Numbers: Absolute difference logic handles negative integers correctly without special casing.
  • Even Length Array: The code picks the element at n // 2. Since any value between nums[n//2 -1] and nums[n//2] is optimal, picking one of these existing values ensures integer constraints are met while maintaining optimality.