LeetCode 462 - Minimum Moves to Equal Array Elements II

This problem asks us to determine the minimum number of moves required to make all elements in an integer array equal, where a move consists of incrementing or decrementing a single element by 1.

leetcodemediumarraymathsorting

LeetCode Problem 462

Difficulty: 🟡 Medium
Topics: Array, Math, Sorting

Solution

Problem Understanding

This problem asks us to determine the minimum number of moves required to make all elements in an integer array equal, where a move consists of incrementing or decrementing a single element by 1. In other words, we want to find a single target value that, when all elements are adjusted to it, requires the fewest total steps.

The input is a list of integers, which can include negative numbers and may have up to 100,000 elements. The output is a single integer representing the minimum number of moves. The constraints imply that a naive approach, such as trying every possible target value within the range of array elements, will be too slow because the array length and element range are large.

Edge cases to keep in mind include arrays where all elements are already equal, arrays of length 1, arrays with negative numbers, and arrays where the minimum or maximum values are extreme (like -10^9 or 10^9). The problem guarantees that the number of moves will fit in a 32-bit integer, so we do not need to handle integer overflow in the output.

Approaches

The brute-force approach would involve trying every integer value between the minimum and maximum element of the array as a target and computing the sum of moves required to convert each element to that target. While this is correct because it evaluates all possibilities, it is inefficient because the element range can be up to 2 * 10^9, making this approach infeasible.

The optimal approach relies on a key insight from statistics: the sum of absolute differences from a set of numbers is minimized at the median. The median divides the array such that half the elements are smaller and half are larger. Converting all elements to the median ensures that every increment and decrement is balanced in a way that produces the minimum total moves. To implement this, we can sort the array and pick the middle element as the median. For arrays with an even number of elements, any number between the two middle values will produce the same minimum moves, so selecting either middle element works.

Approach Time Complexity Space Complexity Notes
Brute Force O((max-min) * n) O(1) Try every integer in the element range; too slow for large ranges
Optimal O(n log n) O(1) Sort array, pick median, sum absolute differences

Algorithm Walkthrough

  1. Sort the array nums in non-decreasing order. Sorting allows us to identify the median directly, which is the key to minimizing absolute differences.
  2. Determine the median. If the length of the array is odd, it is the middle element. If it is even, pick either of the two middle elements.
  3. Initialize a variable moves to 0 to accumulate the total number of moves.
  4. Iterate through each element of the array and add the absolute difference between the element and the median to moves. This represents the number of moves required to bring that element to the median.
  5. Return moves as the final answer.

Why it works: The median minimizes the sum of absolute deviations. Any number larger than the median would increase the total moves contributed by the smaller half of the array, and any number smaller than the median would increase the total moves contributed by the larger half. Thus, the median is the optimal target.

Python Solution

from typing import List

class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        nums.sort()
        median = nums[len(nums) // 2]
        moves = 0
        for num in nums:
            moves += abs(num - median)
        return moves

The solution first sorts nums to access the median directly. The median is found at index len(nums) // 2, and a loop computes the sum of absolute differences between each element and the median. The result is the minimum number of moves, leveraging the statistical property of the median.

Go Solution

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
}

In Go, we use sort.Ints to sort the slice. Since math.Abs works with floats, we convert the integer difference to float64 and back to int. The logic is identical to Python, iterating over the slice to sum absolute differences to the median.

Worked Examples

Example 1: nums = [1,2,3]

Sort the array: [1,2,3]

Median: 2

Moves: abs(1-2) + abs(2-2) + abs(3-2) = 1 + 0 + 1 = 2

Step nums median moves
Initial [1,2,3] 2 0
Element 1 [1,2,3] 2 1
Element 2 [1,2,3] 2 1
Element 3 [1,2,3] 2 2

Example 2: nums = [1,10,2,9]

Sort: [1,2,9,10]

Median: 9 (or 2 also works, sum is same)

Moves: abs(1-9)+abs(2-9)+abs(9-9)+abs(10-9) = 8+7+0+1=16

Step nums median moves
Initial [1,2,9,10] 9 0
Element 1 9 8
Element 2 9 15
Element 3 9 15
Element 4 9 16

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting the array dominates; summing differences is O(n)
Space O(1) Only constant extra space is used; sorting in place if allowed

Sorting determines the overall time complexity. Computing the sum of absolute differences is linear, which is negligible compared to sorting for large arrays. No additional data structures are required, making the space complexity constant.

Test Cases

# Provided examples
assert Solution().minMoves2([1,2,3]) == 2  # Simple 3-element array
assert Solution().minMoves2([1,10,2,9]) == 16  # Mixed small and large numbers

# Edge cases
assert Solution().minMoves2([1]) == 0  # Single element, no moves needed
assert Solution().minMoves2([5,5,5,5]) == 0  # All elements equal
assert Solution().minMoves2([-1,-10,0,10]) == 20  # Includes negative numbers

# Large numbers
assert Solution().minMoves2([-10**9, 10**9]) == 2000000000  # Large extremes
assert Solution().minMoves2([1]*100000) == 0  # Large array with identical values
Test Why
[1,2,3] Simple, small array
[1,10,2,9] Mixed small and large numbers
[1] Single element edge case
[5,5,5,5] All elements equal edge case
[-1,-10,0,10] Negative numbers included
[-10^9, 10^9] Extreme values test integer limits
[1]*100000 Large input with identical values

Edge Cases

Single element array: With only one number, no moves are required. The implementation handles this automatically since the loop over nums computes abs(num - median), which is zero.

All elements equal: If all elements are the same, the median is the element itself. The loop sums abs(num - median), resulting in 0.

Negative numbers and extremes: The array may include very large positive or negative numbers. The algorithm works correctly because absolute difference calculations handle negative numbers naturally. Sorting handles the full integer range without overflow, and the 32-bit answer guarantee ensures moves does not exceed integer limits.