```
# solve it in x and y dimension, and min == min(x) + min(y)
class Solution(object):
def get_min(self, proj, count, points):
# calculate the value of meeting at point 0 first
min_d = 0
for k, v in proj.items():
# skip the first index
if k == 0:
continue
min_d += k * v
# for a given point p (start from 0), l_val and r_val hold total
# distance of all points on left and right side of p respectively.
# l_count and r_count represent the number of points on left and right
# side of p respectively.
l_val, r_val = 0, min_d
l_count, r_count = 0, count - proj.get(0, 0)
# iterate through each possible meet point.
# Update left count and increment total distance of all left points by 1.
# Decrement total distance of all right points by 1 and update right count.
for i in range(1, points):
# for left pt, we update count first, then update val
# for right pt, we update val then update count
l_count += proj.get(i - 1, 0)
l_val += l_count
r_val -= r_count
r_count -= proj.get(i, 0)
min_d = min(min_d, l_val + r_val)
# when meeting point is at the last index
l_count += proj.get(points - 1, 0)
l_val += l_count
min_d = min(min_d, l_val)
return min_d
def minTotalDistance(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if len(grid) == 0 or len(grid[0]) == 0:
return 0
# x, y contains projections of 1s in each dimension
x = {}
y = {}
count = 0
for i, r in enumerate(grid):
for j, v in enumerate(r):
if v != 1:
continue
count += 1
x[i] = x.get(i, 0) + 1
y[j] = y.get(j, 0) + 1
min_x = self.get_min(x, count, len(grid))
min_y = self.get_min(y, count, len(grid[0]))
return min_x + min_y
```