Problem statement

https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/

Solution

What we actually need to find, is the point on line, such that sum of distances to this point is minimal. The best point is the median of our data. Why? On each step we can take the biggest and the smallest point and remove them: optimal point is somewhere in the middle. Then we continue until we have 1 or 0 points.

Complexity

Time complexity is O(n * log n) to sort points and then use two pointers approach in O(n), space complexity is O(n).

Code

class Solution:
    def minMoves2(self, A):
        return sum(abs(a-b) for a,b in zip(sorted(A), sorted(A)[::-1]))//2

Remark

There is also O(n) time complexity solution, because there is a way to find median in linear time.