Leetcode 462. Minimum Moves to Equal Array Elements II

Problem

You have an integer array where elements have different values. In one operation, you can increment or decrement any single element by exactly 1. Your goal is to make all elements in the array equal using the minimum number of operations.

Return the minimum number of operations required to achieve this goal.

Requirements

1. Each operation changes exactly one element by +1 or -1
2. Find the optimal target value that minimizes total operations
3. All array elements must become equal to the chosen target
4. Handle arrays with positive, negative, and zero values

Constraints

• 1 ≤ nums.length ≤ 105
• -109 ≤ nums[i] ≤ 109
• Target time complexity: O(n log n) or better
• Target space complexity: O(1) excluding sorting space

Examples

Example 1:

` Input: nums = [1, 2, 3] Output: 2 Explanation: We can make all elements equal to 2.

• Change 1 to 2: 1 operation
• Keep 2 as is: 0 operations
• Change 3 to 2: 1 operation Total: 2 operations `

Example 2:

Input: nums = [1, 10, 2, 9] Output: 16 Explanation: The optimal target is either 2 or 9 (both medians after sorting: [1,2,9,10]). Using target = 2: |1-2| + |10-2| + |2-2| + |9-2| = 1 + 8 + 0 + 7 = 16 Using target = 9: |1-9| + |10-9| + |2-9| + |9-9| = 8 + 1 + 7 + 0 = 16

Example 3:

Input: nums = [5, 5, 5, 5] Output: 0 Explanation: All elements are already equal, no operations needed.

Hint 1: Finding the Optimal Target The problem is asking for a target value that minimizes the sum of absolute differences from all array elements. Think about which statistical measure minimizes the sum of absolute deviations.

What value in a dataset has this mathematical property?

Hint 2: Mathematical Insight The median of a dataset minimizes the sum of absolute deviations. This is a well-known property in statistics (L1 optimization).

For an array sorted in ascending order, the median is:

• The middle element if the length is odd
• Either of the two middle elements if the length is even (both give the same result)

Hint 3: Implementation Strategy

1. Sort the array to easily find the median
2. Find the median element (middle element after sorting)
3. Calculate the sum of absolute differences between each element and the median

The sum will give you the minimum number of operations needed.

Full Solution ` def minMoves(nums): # Sort the array to find the median nums.sort()

# Find the median (middle element)
# For even-length arrays, either middle element works
n = len(nums)
median = nums[n // 2]

# Calculate total operations needed
# Each operation is the absolute difference from the median
total_moves = 0
for num in nums:
    total_moves += abs(num - median)

return total_moves

`

Explanation:

The key insight is that this problem is equivalent to finding a target value that minimizes the sum of absolute deviations—a classic L1 optimization problem. The solution to this is always the median of the dataset.

Why the median?

Consider moving all elements to some target value t. The total cost is:

• Sum of |nums[i] - t| for all i

The median minimizes this sum because:

• For any value below the median, moving it up decreases the distance to elements above more than it increases the distance to elements below
• Similarly for any value above the median
• The median is the "balance point" where moving in either direction doesn't improve the total

Algorithm:

1. Sort the array: O(n log n)
2. Select the median: O(1)
3. Sum absolute differences: O(n)

Complexity Analysis:

• Time Complexity: O(n log n) due to sorting
• Space Complexity: O(1) if sorting in-place, otherwise O(n) for the sort

Alternative O(n) approach: We can use the QuickSelect algorithm to find the median in average O(n) time without fully sorting, reducing the time complexity. However, the O(n log n) solution is simpler and sufficient for most interview contexts.