Problem statement

https://leetcode.com/problems/best-meeting-point/

Solution

First of all, note, that we can solve two separate problems, one for $x$-coordinates and one for $y$-coordinates. Then, suppose we have points $x_1, \dots, x_k$ and we need to find point $x_{best}$ such that sum of distances is minimal. Let $m$ and $n$ be size of our grid, then we can do bruteforce and check every possible candidate for $x_{best}$ in $O(n)$. Overall complexity in this case is $O(m+n)\cdot k + O(mn)$.

We can do smarter: sort all points, and look at the first and the last. Then $x_{best}$ will be somewhere in the middle, and sum of distances between these two edge points and $x_{best}$ will always be a constant: difference between edge points. So we can remove them and continue the same logic. Finally, we find the best point in $O(k)$, if points are sorted.

Complexity

Time complexity complexity is $O(k\log k + mn)$, we need $mn$ here, because first we need to find all people on our grid.

Code

class Solution:
    def minTotalDistance(self, grid):
        m, n = len(grid), len(grid[0])
        people = []
        for i, j in product(range(m), range(n)):
            if grid[i][j] == 1:
                people.append((i, j))
                
        k = len(people)
        
        x_coors = sorted([x for x, _ in people])
        y_coors = sorted([y for _, y in people])
        
        x_sum = sum(x_coors[k//2:]) - sum(x_coors[:(k+1)//2])
        y_sum = sum(y_coors[k//2:]) - sum(y_coors[:(k+1)//2])
        return x_sum + y_sum