Python solution with detailed explanation

  • 1


    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.
    • 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:
            return rows, cols
        def get_median_co_ordinates(self, rows, cols):
            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

  • 0

    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){
        int n = arr.size();
        return arr.get(n/2);


Log in to reply

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