Watch 10 video solutions for Best Meeting Point, a hard level problem involving Array, Math, Sorting. This walkthrough by CrioDo has 304,598 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an m x n binary grid grid where each 1 marks the home of one friend, return the minimal total travel distance.
The total travel distance is the sum of the distances between the houses of the friends and the meeting point.
The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.
Example 1:
Input: grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]] Output: 6 Explanation: Given three friends living at (0,0), (0,4), and (2,2). The point (0,2) is an ideal meeting point, as the total travel distance of 2 + 2 + 2 = 6 is minimal. So return 6.
Example 2:
Input: grid = [[1,1]] Output: 1
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 200grid[i][j] is either 0 or 1.grid.Problem Overview: You’re given a binary grid where 1 represents a person's home. The goal is to choose a meeting cell that minimizes the sum of Manhattan distances from all homes to that point. Movement is allowed only horizontally and vertically, so the Manhattan metric drives the optimal strategy.
Approach 1: Brute Force – Try Every Cell (O((mn)^2) time, O(1) space)
Enumerate every cell in the matrix as a potential meeting point. For each candidate cell, iterate through the grid again and compute the Manhattan distance to every home using |r1 - r2| + |c1 - c2|. Track the minimum total distance seen so far. This approach is straightforward but expensive because for each of the m * n cells you scan the entire grid again. It works for small grids and demonstrates the distance calculation logic, but it quickly becomes impractical for large inputs.
Approach 2: Median with Sorting (O(mn log mn) time, O(mn) space)
Manhattan distance separates cleanly into row distance and column distance. That means you can minimize them independently. Collect the row indices and column indices of every home into two arrays. After collecting them, sort both arrays using a typical sorting algorithm. The optimal meeting coordinate is the median of the rows and the median of the columns. This works because the median minimizes the sum of absolute differences, a core property used in many math optimization problems. Compute the total distance by summing the absolute difference between each coordinate and the chosen median.
Approach 3: Median without Sorting (O(mn) time, O(mn) space)
You can avoid sorting entirely by exploiting grid traversal order. Scan the grid row-by-row and append row indices when you encounter a home. This automatically keeps rows sorted. Then scan column-by-column and append column indices, which keeps the column list sorted as well. With both arrays already ordered, the median element can be accessed directly. Finally compute the total Manhattan distance from all rows to the row median and from all columns to the column median. This reduces the time complexity to linear in the number of cells while preserving the same optimal meeting point.
Recommended for interviews: The median-based approach is the expected solution. Start by explaining the brute force to show understanding of Manhattan distance, then pivot to the insight that distance splits into row and column components. Identifying the median as the minimizer of absolute differences demonstrates strong algorithmic reasoning and familiarity with grid problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force (Check Every Cell) | O((mn)^2) | O(1) | Good for explaining the Manhattan distance idea or validating correctness on small grids |
| Median with Sorting | O(mn log mn) | O(mn) | General solution when collecting coordinates then sorting is simplest to implement |
| Median without Sorting | O(mn) | O(mn) | Optimal approach when you leverage grid traversal order to keep coordinates sorted |