Python solution with detailed explanation


  • 1
    G

    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
    

  • 0
    S

    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){
                    xCord.add(c);
                    yCord.add(r);
                }
            }
        }
        
        // 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);
    }
    

    }


Log in to reply
 

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