Introduction
LeetCode 296: Best Meeting Point is a problem where you are given a 2D grid representing a map, with some cells marked as 1 (representing people) and others as 0. The goal is to determine the "best" meeting point for all the people, where the meeting point minimizes the total Manhattan distance to all the people.
This problem tests your understanding of spatial optimization and distance minimization, where the objective is to minimize the total sum of distances for all the people to the meeting point.
Problem Statement
You are given an m x n grid, where each cell can either be 0 (empty) or 1 (person). Find the best meeting point, where the total Manhattan distance from all the people to the meeting point is minimized.
The Manhattan distance between two points (x1, y1) and (x2, y2) is defined as |x1 - x2| + |y1 - y2|.
The function should return the minimum total distance from all the people to the best meeting point.
Example
python
Input:
grid = [
[1,0,0,0,1],
[0,0,0,0,0],
[0,0,1,0,0],
]
Output:
6
Explanation:
- There are three people located at
(0, 0), (0, 4), and (2, 2).
- The best meeting point is
(1, 2) because it minimizes the total Manhattan distance to all the people. The total distance is 6 (calculated as the sum of distances from (0, 0), (0, 4), and (2, 2) to (1, 2)).
✅ Step-by-Step Solution
🧠 Intuition
To solve this problem efficiently, we need to:
- Find the best meeting point such that the total Manhattan distance to all the people is minimized.
- Since the Manhattan distance is separable, we can minimize the distance in the x-axis (horizontal) and y-axis (vertical) separately.
- Manhattan Distance: The Manhattan distance between two points
(x1, y1) and (x2, y2) is the sum of the absolute differences of their x and y coordinates: |x1 - x2| + |y1 - y2|.
- To minimize the total Manhattan distance, we need to select the median of the x-coordinates and the median of the y-coordinates of all the people, because:
- The median minimizes the sum of absolute differences for a set of numbers.
Thus, we will:
- Separate the x and y coordinates of all the people.
- Find the median of the x-coordinates and the median of the y-coordinates.
- The best meeting point will be the point at
(median_x, median_y).
✅ Approach
- Extract People’s Coordinates:
- First, collect all the coordinates of the people (cells with
1) in the grid.
- Find the Median:
- The optimal meeting point will be located at the median of the x-coordinates and the median of the y-coordinates. This is because the median minimizes the sum of absolute distances in one dimension.
- Calculate Total Distance:
- Once we have the optimal meeting point, calculate the total Manhattan distance from all the people to this point.
✅ Python Code
python
class Solution:
def minTotalDistance(self, grid):
people = []
# Collect the coordinates of all the people (cells with 1)
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
people.append((i, j))
# If no people are present, return 0
if not people:
return 0
# Extract the x and y coordinates
x_coords = [person[0] for person in people]
y_coords = [person[1] for person in people]
# Find the medians of x and y coordinates
x_coords.sort()
y_coords.sort()
median_x = x_coords[len(x_coords) // 2]
median_y = y_coords[len(y_coords) // 2]
# Calculate the total Manhattan distance from the best meeting point
total_distance = 0
for x, y in people:
total_distance += abs(x - median_x) + abs(y - median_y)
return total_distance
🧪 How It Works
- Extract Coordinates:
- We loop through the grid and extract the coordinates of all cells containing
1 (people).
- Find the Median:
- After collecting the coordinates, we sort the x and y coordinates.
- The median of the x-coordinates is the middle element of the sorted x-list (and similarly for the y-coordinates).
- Calculate Total Distance:
- Using the median coordinates as the meeting point, we calculate the Manhattan distance from each person to this meeting point and sum it up.
- Return the Result:
- The sum of all distances is returned as the total distance.
⏱️ Time and Space Complexity
MetricValueTime ComplexityO(m * n log(m * n)), where m and n are the grid dimensions. The time complexity is dominated by the sorting operation for the coordinates.Space ComplexityO(m * n), where m and n are the grid dimensions. The space complexity comes from storing the coordinates of all the people.
- Time Complexity: Sorting the x and y coordinates takes O(k log k) time, where
k is the number of people. Collecting the coordinates and calculating the total distance each take O(k), so the overall time complexity is O(k log k).
- Space Complexity: We store the coordinates of the people, so the space complexity is O(k), where
k is the number of people.
🔍 Edge Cases
- Empty Grid: If the grid contains no
1s (i.e., no people), the result should be 0, as no meeting point is necessary.
- For example, for an empty grid
[[0,0],[0,0]], the result should be 0.
- Single Person: If only one person exists, the best meeting point is the person’s own position, and the total distance is
0.
- For example, for a grid
[[0,0,1]], the result should be 0.
- Multiple People in a Straight Line: If all people are aligned along a row or column, the median will still be the center of the line, minimizing the total distance.
- For example, for the grid
[[0,1,0,1,0]], the median position will be 1,2, minimizing the total distance.
- Grid with Many People: The approach still works efficiently even for grids with many people due to the use of sorting and the separation of x and y coordinates.
✅ Conclusion
LeetCode 296: Best Meeting Point is an optimization problem that challenges us to find the best meeting point for people in a 2D grid, minimizing the total Manhattan distance. By using the median of the x and y coordinates, we can efficiently compute the best meeting point and the associated total distance.
This approach leverages sorting to efficiently find the optimal meeting point and guarantees an efficient solution even for larger grids.