# Question

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance (p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Example:

Input:

1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

Output: 6

Explanation: Given three people living at (0,0), (0,4), and (2,2):
The point (0,2) is an ideal meeting point, as the total travel distance
of 2+2+2=6 is minimal. So return 6.


# Solution

The meeting point is medium of all 1s. Time complexity is $$O(mnlog(mn))$$ due to sorting. The space complexity is $$O(mn)$$.

class Solution(object):
def minTotalDistance(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if len(grid) == 0 or len(grid) == 0:
return 0

homes = list()
for i in range(len(grid)):
for j in range(len(grid)):
if grid[i][j] == 1:
homes.append((i, j))

if len(homes) == 0:
return 0

x = sorted([p for p in homes])
y = sorted([p for p in homes])

if len(homes) % 2 == 1:
X, Y = x[len(homes) // 2], y[len(homes) // 2]
else:
xm = sum(x[len(homes) // 2 - 1:len(homes) // 2 + 1]) / 2
ym = sum(y[len(homes) // 2 - 1:len(homes) // 2 + 1]) / 2

def round(a):
floor = int(a)
if a - floor < floor + 1 - a:
return floor
else:
return floor + 1

X, Y = round(xm), round(ym)

return sum([abs(X - p) + abs(Y - p) for p in homes])


However, we can get rid of the sorting by collecting x and y in order. This gives us a time complexity of $$O(mn)$$.

class Solution(object):
def minTotalDistance(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if len(grid) == 0 or len(grid) == 0:
return 0

x = list()
for i in range(len(grid)):
for j in range(len(grid)):
if grid[i][j] == 1:
x.append(i)

if len(x) == 0:
return 0

size = len(x)
y = list()
for j in range(len(grid)):
for i in range(len(grid)):
if grid[i][j] == 1:
y.append(j)

if size % 2 == 1:
X, Y = x[size // 2], y[size // 2]
else:
xm = sum(x[size // 2 - 1:size // 2 + 1]) / 2
ym = sum(y[size // 2 - 1:size // 2 + 1]) / 2

def round(a):
floor = int(a)
if a - floor < floor + 1 - a:
return floor
else:
return floor + 1

X, Y = round(xm), round(ym)

return sum([abs(X - x_) for x_ in x]) + sum([abs(Y - y_) for y_ in y])