Best Meeting Point
Hard · Matrix · Array · Math · Sorting · Matrix
Problem
You are given an m x n grid of 0s and 1s, where each 1 is the home of one friend. The friends want to meet at a single cell, any cell at all, including one with a home, so that the total distance they travel is as small as possible.
Distance is measured along the grid lines: from (r1, c1) to (r2, c2) is |r1 - r2| + |c1 - c2|.
Return the smallest possible total distance.
Examples
Input: grid = [[1,0,1],[0,0,0],[0,1,0]] Output: 4
Meeting at (0, 1) costs 1 + 1 + 2 = 4, and no cell does better.
Input: grid = [[1,1]] Output: 1
Meeting at either home costs 1.
Input: grid = [[0,1],[0,0],[1,0]] Output: 3
Any cell on a shortest route between the two homes works, and the distance between them is 3.
Constraints
- m == len(grid)
- n == len(grid[i])
- 1 <= m, n <= 200
- grid[i][j] is 0 or 1
- There are at least two friends
Approaches
- Try every cell — time O(m · n · k), space O(k)
Follow-up
If the meeting cell must be empty, or walls block some paths, the coordinates are no longer independent and the trick fails; a BFS from every home (summing the distances per cell) is then needed. If the distance is straight-line instead of along the grid, the best point is the geometric median, which has no closed form and is found by iterative methods.
Related problems
Start free on Cariara · Coding problems · System design studio
