# Solution For Best Meeting Point

The Best Meeting Point problem on LeetCode is a problem of finding the best place to meet for a group of people in a 2D grid. The objective is to minimize the total distance that the people have to travel to reach the meeting point. In this problem, the grid is represented by a binary matrix, where 1 represents an empty cell and 0 represents an obstacle.

Approach:

One approach to solve this problem is to find the medians of the rows and columns separately. To do this, we can iterate through all the cells of the grid, count the number of people in each row and column, and calculate the total distance to each cell of that row or column. Then, we can find the cell with the minimum distance, which will be the median of that row or column.

Next, we can calculate the total distance of all the people to this cell. We can repeat the same process for the columns, and find the cell which has the minimum total distance.

Implementation:

The following is the stepwise implementation of the Best Meeting Point problem in Python:

- Find the row medians:

“`

def minTotalDistance(grid):

rows = len(grid)

cols = len(grid[0])

```
row_sum = [0] * rows
col_sum = [0] * cols
for i in range(rows):
for j in range(cols):
if grid[i][j] == 1:
row_sum[i] += 1
col_sum[j] += 1
row_median = findMedian(row_sum)
col_median = findMedian(col_sum)
return calcDistance(grid, row_median, col_median)
```

“`

Here, we are finding the medians of the rows and columns separately, and then we are calling the function `calcDistance`

to calculate the minimum distance. The `findMedian`

function is used to find the median of the given array.

- Find the median of an array:

`def findMedian(arr):`

median = 0

n = len(arr)

if n % 2 == 0:

median = (arr[n // 2 - 1] + arr[n // 2]) // 2

else:

median = arr[n // 2]
return median

This function calculates the median of an array by checking whether the length of the array is even or odd.

- Calculate the distance:

“`

def calcDistance(grid, row_median, col_median):

total_distance = 0

rows = len(grid)

cols = len(grid[0])

```
for i in range(rows):
for j in range(cols):
if grid[i][j] == 1:
total_distance += abs(row_median - i) + abs(col_median - j)
return total_distance
```

“`

This function calculates the minimum distance by iterating through all the cells of the grid, and calculating the distance of each cell to the median of the rows and columns.

Time Complexity:

The time complexity of this algorithm is O(m * n), where m and n are the dimensions of the grid.

Space Complexity:

The space complexity of this algorithm is O(m + n), where m and n are the dimensions of the grid.

## Step by Step Implementation For Best Meeting Point

/** * Definition for a point. * class Point { * int x; * int y; * Point() { x = 0; y = 0; } * Point(int a, int b) { x = a; y = b; } * } */ public class Solution { public int minTotalDistance(int[][] grid) { // check for empty grid if (grid == null || grid.length == 0 || grid[0].length == 0) { return 0; } // get all row and column indices of 1's in the grid Listrows = new ArrayList<>(); List cols = new ArrayList<>(); for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == 1) { rows.add(i); cols.add(j); } } } // sort the row and column indices Collections.sort(rows); Collections.sort(cols); // find the median row and column indices int midRow = rows.get(rows.size() / 2); int midCol = cols.get(cols.size() / 2); // calculate the sum of Manhattan distances from median point to all other points int sum = 0; for (int i = 0; i < rows.size(); i++) { sum += Math.abs(midRow - rows.get(i)) + Math.abs(midCol - cols.get(i)); } return sum; } }

def bestMeetingPoint(self, grid): # This problem can be solved by finding the Manhattan distance # from all points to the median point. # We can find the median point by sorting all the x and y coordinates # and taking the middle value. # Get all the x and y coordinates x_coords = [] y_coords = [] for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == 1: x_coords.append(i) y_coords.append(j) # Sort the coordinates x_coords.sort() y_coords.sort() # Get the median coordinates x_median = x_coords[len(x_coords) // 2] y_median = y_coords[len(y_coords) // 2] # Find the Manhattan distance from the median point to all other points distance = 0 for x, y in zip(x_coords, y_coords): distance += abs(x - x_median) + abs(y - y_median) return distance

var bestMeetingPoint = function(grid) { // your code goes here };

There are a number of ways to solve this problem. One approach would be to use a priority queue to keep track of the points that still need to be visited. Then, starting from the point with the smallest x-coordinate, we would iterate through the points and add them to the queue. Once we reach the point with the largest x-coordinate, we would begin popping points off of the queue and calculating the Manhattan distance from each point to the current point. We would keep track of the point with the smallest distance and return that point as our best meeting point. Another approach would be to use a breadth-first search algorithm. We would start at the point with the smallest x-coordinate and add all of its neighbors to a queue. Then, we would continue this process until we reach the point with the largest x-coordinate. Once we reach the end, we would backtrack through the points and calculate the Manhattan distance from each point to the current point. We would keep track of the point with the smallest distance and return that point as our best meeting point.

using System; class GFG { // A utility function to find the // vertex with minimum distance value, // from the set of vertices not yet included in shortest // path tree static int V; static int minKey(int[] key, bool[] mstSet) { // Initialize min value int min = int.MaxValue, min_index=-1; for (int v = 0; v < V; v++) if (mstSet[v] == false && key[v] < min) { min = key[v]; min_index = v; } return min_index; } // A utility function to print // the constructed MST stored in // parent[] static void printMST(int[] parent, int n, int[,] graph) { Console.WriteLine("Edge \tWeight"); for (int i = 1; i < V; i++) Console.WriteLine(parent[i]+" - "+ i+"\t"+graph[i, parent[i]]); } // Function to construct and // print MST for a graph represented // using adjacency matrix representation static void primMST(int[,] graph) { //Array to store constructed MST int[] parent = new int[V]; //Key values used to pick minimum weight edge in cut int[] key = new int[V]; // To represent set of vertices not // yet included in MST bool[] mstSet = new bool[V]; // Initialize all keys as INFINITE for (int i = 0; i < V; i++) { key[i] = int.MaxValue; mstSet[i] = false; } // Always include first 1st vertex in MST. // Make key 0 so that this vertex is // picked as first vertex key[0] = 0; parent[0] = -1; // First node is always root of MST // The MST will have V vertices for (int count = 0; count < V-1; count++) { // Pick thd minimum distance vertex from // the set of vertices not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of // the adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (int v = 0; v < V; v++) // graph[u][v] is non zero only for adjacent vertices of m // mstSet[v] is false for vertices not yet included in MST // Update the key only if graph[u][v] is smaller than key[v] if (graph[u, v]!=0 && mstSet[v] == false && graph[u, v] < key[v]) { parent[v] = u; key[v] = graph[u, v]; } } // print the constructed MST printMST(parent, V, graph); } // Driver Code public static void Main() { /* Let us create the following graph 2 3 (0)--(1)--(2) | / \ | 6| 8/ \5 |7 | / \ | (3)-------(4) 9 */ V = 5; int[,] graph = new int[,] {{0, 2, 0, 6, 0}, {2, 0, 3, 8, 5}, {0, 3, 0, 0, 7}, {6, 8, 0, 0, 9}, {0, 5, 7, 9, 0}}; // Print the solution primMST(graph); } } // This code is contributed by Aakash Hasija