# Python solution with detailed explanation

• Solution

Best Meeting Point https://leetcode.com/problems/best-meeting-point/

Median minimizes the absolute distance of points: O(MN)

• Median minimizes the absolute distance of points. Mean minimizes the squared distance from points.
• http://math.stackexchange.com/questions/113270/the-median-minimizes-the-sum-of-absolute-deviations?rq=1
• We simply find the list of x and y co-ordinates where we have a building. Then we individually sort them to find the median element in each list. This is the point which is closest meeting point.
• To find the total walking distance, simply add abs(x_median-x) and abs(y_median-y) to the final result. Note it doesnt matter that we sorted the co-ordinate lists since the order in which we add does not matter.
``````class Solution(object):
def get_building_points(self, grid):
M,N = len(grid),len(grid[0])
rows,cols = [], []
for i in range(M):
for j in range(N):
if grid[i][j] == 1:
rows.append(i)
cols.append(j)
return rows, cols

def get_median_co_ordinates(self, rows, cols):
rows.sort()
cols.sort()
x_median, y_median = rows[len(rows)//2], cols[len(cols)//2]
return x_median, y_median

def minTotalDistance(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
rows, cols = self.get_building_points(grid)
x_median, y_median = self.get_median_co_ordinates(rows, cols)

result = 0
for x in rows:
result += abs(x_median-x)
for y in cols:
result += abs(y_median-y)
return result
``````

• This is my java implementation of your idea. Thanks
'''

``````  public class Solution {
public int minTotalDistance(int[][] grid) {

List<Integer> xCord = new ArrayList<>();
List<Integer> yCord = new ArrayList<>();

// get the points for which meeting point needs calculation
for(int r = 0; r < grid.length; r++){
for(int c = 0; c < grid[0].length; c++){
if(grid[r][c] == 1){
}
}
}

// find the median
int xMedian = getMedian(xCord);
int yMedian = getMedian(yCord);
//System.out.println(xMedian + " " + yMedian);

// calculate and add manhattan distance to total
int result = 0;
for(int x : xCord){
result += Math.abs(x - xMedian);
}
for(int y : yCord){
result += Math.abs(y - yMedian);
}

return result;
}

public int getMedian(List<Integer> arr){
Collections.sort(arr);
int n = arr.size();
return arr.get(n/2);
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.