LC 0296 [H] Best Meeting Point - ALawliet/algorithms GitHub Wiki

class Solution:
    def minTotalDistance(self, grid: List[List[int]]) -> int:
        n_rows = len(grid)
        n_cols = len(grid[0])
        
        # S: O(mn)
        rows = []
        cols = []
        
        # 2D -> 1D
        for r in range(n_rows):
            for c in range(n_cols):
                if grid[r][c] == 1:
                    rows.append(r)
                    cols.append(c)
        
        # T: O(mnlogmn)
        # rows.sort()
        cols.sort()
        
        # find medians
        med_row = rows[len(rows) // 2]
        med_col = cols[len(cols) // 2]
        
        # sum of all distance from median
        return sum(abs(row - med_row) for row in rows) + sum(abs(col - med_col) for col in cols)