Background
This article came from a Leetcode problem: 462. Minimum Moves to Equal Array Elements II. For the sake of reading experience, I paste the problem description here:
Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1.
You may assume the array's length is at most 10,000.
Example:
Input: [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]
My first intuition was to sum the distances between each element and the mean(average) of the list, which failed to pass the test. Here we discuss the problem in a mathematical way.
Problem Statement
The description:
find the minimum number of moves required to make all array elements equal.
means we need to find a \(m\) which satisfies:
\[ \arg\min_m \sum_{i=1}^n |x_i - m| \tag{1-1} \]\(x\) is an \(n\) dimensional vector.
In other words, the \(m\) we need is to minimize the L1-norm of the residual. While the average of a list minimize the L2-norm of the residual.
Derivation
In order to find \(m\), we can borrow the idea of how the average \(\mu\) was found:
\[ \arg\min_\mu (x - \mu)^\top(x - \mu) \tag{2-1} \]The minimum can be found by setting its derivative to 0:
\[ \frac{\text{d}}{\text{d}\mu} (x - \mu)^\top(x - \mu) = \frac{\text{d}}{\text{d}\mu} (x^\top x - 2\mu\sum_{i=1}^n x_i + n\mu ^2) = 0 \tag{2-2} \] \[ 2n\mu - 2\sum_{i=1}^n x_i = 0 \] \[ \mu = \frac{\sum_{i=1}^n x_i}{n} \tag{2-3} \]We write formulation (1-1) as:
\[ \arg\min_m \sum_{i=1}^n \sqrt{(x_i - m)^2} \tag{2-4} \]Set the derivative to 0:
\[ \frac{\text{d}}{\text{d}m} \sum_{i=1}^n \sqrt{(x_i - m)^2} = \sum_{i=1}^n \frac{x_i - m}{\sqrt{(x_i - m)^2}} \\ = \sum_{i=1}^n \text{sign} (x_i - m) = 0 \tag{2-5} \]Formula (2-5) indicates that when \(m\) lies on the coordinate such that the number of \(x_i\) greater than \(m\) equals to the number of \(x_i\) less than \(m\), \(m\) minimizes the L1-norm of the residual. It is worth noting that there are more than one solution. The median of the vector \(x\) can be a solution.
Summary
A clean solution of the leetcode problem can be:
class Solution:
def minMoves2(self, nums: List[int]) -> int:
nums.sort()
m = nums[len(nums) // 2]
return sum([abs(n - m) for n in nums])