Best Meeting Point LeetCode Solution

Difficulty Level Hard
Frequently asked in Amazon Bloomberg Expedia Facebook Google Microsoft Snapchat TwitterViews 224

Problem Statement

The Best Meeting Point LeetCode Solution says Given a binary grid grid of size m x n where each 1 determines the home of one friend, we want to return the minimal total travel distance where the total travel distance is the sum of the distances between the houses of the friends and the meeting point.

The total travel distance is calculated as the sum of Manhatten distance between the points.

Best Meeting Point LeetCode Solution

Manhatten distance: The distance calculated as the sum of the absolute differences between the two vectors. i.e. Manhatten distance between points (x1,y1) and (x2,y2) can be calculated as:

D= | x1-x2| + |y1-y2|

In the above example :

Input:

 grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]

Output:

 6

Explanation:

Given are three friends located at positions (0,0), (0,4), and (2,2).
The point (0,2) is an appropriate meeting point because the total travel distance is minimal i.e.  2 + 2 + 2 = 6.
Hence, we return 6.

Another example :

Input:

 grid = [[1,1]]

Output:

 1

Solution Approach

The Concept

The point lying at the median coordinates (midx,midy) where midx is the median of x-coordinate values vector and midy is the median of the y-coordinate values vectoris the point of minimal Total travel distance.

Proof

Best Meeting Point LeetCode Solution

Here in the graph,

Let a,b,c,d,e be five location points and x be a point of total travel distance Our goal is to find a location where the distance from all points to x i.e. D is minimum.

Case 1 : Let x lie at (0,0) D1= a+b+c+d+e

Case 2 : Let x lie before point a (closest to a) D2= (a-x)+(b-x)+(c-x)+(d-x)+(e-x) D2= a+b+c+d+e – 5*x D2= D1 -5*x => D2<D1 [ total travel distance  in Case 2<Case 1]

Case 3 : Let x lie after point e (closest to e) D3= (x-a)+(x-b)+(x-c)+(x-d)+(x-e) D3= 5*x- a+b+c+d+e D3= 5*x – D1 [ Here x in Case 3 >>> x in Case 2] => D3>D2 [ total travel distance  in Case 3>Case2]

Case 4 : Let x lie after point c (median point) D4= (c-a)+(c-b)+(c-c)+(d-c)+(e-c) D4= a+b+c+d+e – 5*c D4= a+b+d+e-4*c => D4<D2 [ Clearly, total travel distance in Case 2>Case3]

Clearly, considering the above 4 cases we can state that the total distance from all the points to the median is minimum.

Therefore, the Median point is the point of minimum Total travel Distance.

Approach

  1. Collect the x-coordinates of all positions with ‘1’ in a vector xcoordinates.
  2. Collect the y-coordinates of all positions with ‘1’ in a vector ycoordinates.
  3. Create a vector pair of all positions with ‘1’ distpoints.
  4. Sort xcoordinates and ycoordinates.
  5. Find median  midx in xcoordinates  and midy in ycoordinates [median = middle element in a sorted array, consider the first index of middle elements]
  6. Traverse through distpoints and add Manhatten distance through each point location to the median in total_travel_distance
  7. Return total_travel_distance.

Code

C++ Solution for Best Meeting Point LeetCode Solution

class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
        vector<int>xcoordinates;
        vector<int>ycoordinates;
        //store pair of coordinate points
        vector<pair<int,int>>distpoints;
        
        // store all x-coordinates and y-coordinates in separate vectors O(nm)
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[i].size();j++){
                if(grid[i][j]==1)
                {
                    xcoordinates.push_back(i);
                    ycoordinates.push_back(j);
                    distpoints.push_back({i,j});
                }
            }
        }
      
        //sort both vectors O(nlogn)
        sort(xcoordinates.begin(),xcoordinates.end());
        sort(ycoordinates.begin(),ycoordinates.end());
        
        //find mid element in both vectors  [Median coordinates]
        int index=0;
        int midx=0;
        int midy=0;
        if (xcoordinates.size()%2==0)
            index=xcoordinates.size()/2-1;
        else
            index=xcoordinates.size()/2;
        
        midx= xcoordinates[index];
        midy=ycoordinates[index];
        
        //Find manhatten distance O(n)
        int total_travel_distance=0;
        for(int i=0;i<xcoordinates.size();i++){
            total_travel_distance+=abs(distpoints[i].first-midx)+abs(distpoints[i].second-midy);
        
        }
        return total_travel_distance;
    }
};

Python Solution for Best Meeting Point LeetCode Solution

class Solution(object):
    def minTotalDistance(self, grid):
        colvals = []
        rowvals = []
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    colvals.append(j)
                    rowvals.append(i)
        colvals.sort()
        rowvals.sort()
        
        result = 0
        total_travel_distance = (rowvals[len(rowvals)//2], colvals[len(colvals)//2])
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    result += abs(i-total_travel_distance[0]) + abs(j-total_travel_distance[1])
        return result

Complexities for Best Meeting Point LeetCode Solution :

Time Complexity: O(mn), m, and n are numbers of rows and columns in the grid.

Space Complexity : O(p) , p=number of ‘1’s in grid

Reference: https://en.wikipedia.org/wiki/Taxicab_geometry

https://www.chessprogramming.org/Manhattan-Distance

Translate »