March to the Median — Solution & Editorial

Back to the Problem

The optimal meeting value is any median (it minimizes the sum of absolute deviations); sum |a_i − median|.

Complexity: O(N log N)

Watch out: The MEAN feels right but is wrong for absolute cost — the median wins (try 1, 2, 9).