Best Meeting Point
Best Meeting Point is a hard arrays & hashing problem solved with the matrix traversal pattern.
The best approach, optimal (median per axis), runs in O(m · n) time and O(k) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every cell) up.
Problem
You are given an m x n grid of 0s and 1s. Each 1 is the home of one friend. The friends want to pick a single cell where they all meet, so that the sum of their travel distances is as small as possible.
Distances are measured on the grid lines (Manhattan distance): from (r1, c1) to (r2, c2) is |r1 - r2| + |c1 - c2|. The meeting cell may be any cell, including a home. Return the smallest possible total distance.
Examples
Example 1
- Input
grid = [[0,1,0,0],[0,0,0,1],[1,0,0,0]]- Output
5- Why
- Meeting at (1, 1): the homes at (0, 1), (1, 3) and (2, 0) are 1, 2 and 2 steps away, 5 in total.
Example 2
- Input
grid = [[1,0,1]]- Output
2- Why
- Any cell between the two homes works; their distances always add up to 2.
Example 3
- Input
grid = [[1,1],[1,1]]- Output
4- Why
- Meeting at any cell gives 0 + 1 + 1 + 2 = 4.
Constraints
m == grid.length,n == grid[i].length1 <= m, n <= 200grid[i][j]is0or1.- The grid holds at least two
1s.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every cell) | O(m · n · k) | O(k) |
| Optimal (median per axis) | O(m · n) | O(k) |
1Brute force (try every cell)
O(m · n · k)Each of the m · n cells is compared with all k homes.O(k)The list of k homes.Collect all homes. For every cell in the grid, add up its Manhattan distance to each home, and keep the smallest total.
- Store the (row, col) of every 1.
- For each cell (r, c), compute the sum of |r - hr| + |c - hc| over all homes.
- Return the minimum sum.
class Solution {
public int minTotalDistance(int[][] grid) {
int m = grid.length, n = grid[0].length;
List<int[]> homes = new ArrayList<>();
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 1) homes.add(new int[] { r, c });
}
}
int best = Integer.MAX_VALUE;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
int total = 0;
for (int[] h : homes) total += Math.abs(r - h[0]) + Math.abs(c - h[1]);
best = Math.min(best, total);
}
}
return best;
}
}class Solution:
def minTotalDistance(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
homes = [(r, c) for r in range(m) for c in range(n) if grid[r][c] == 1]
best = float("inf")
for r in range(m):
for c in range(n):
total = 0
for hr, hc in homes:
total += abs(r - hr) + abs(c - hc)
best = min(best, total)
return bestclass Solution {
public:
int minTotalDistance(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<pair<int, int>> homes;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (grid[r][c] == 1) homes.push_back({r, c});
int best = INT_MAX;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
int total = 0;
for (auto& [hr, hc] : homes) total += abs(r - hr) + abs(c - hc);
best = min(best, total);
}
}
return best;
}
};function minTotalDistance(grid) {
const m = grid.length, n = grid[0].length;
const homes = [];
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (grid[r][c] === 1) homes.push([r, c]);
}
}
let best = Infinity;
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
let total = 0;
for (const [hr, hc] of homes) total += Math.abs(r - hr) + Math.abs(c - hc);
best = Math.min(best, total);
}
}
return best;
}2Optimal (median per axis)
O(m · n)Two full scans of the grid plus a linear pass over each list.O(k)The two lists hold k entries each.The total Manhattan distance is the sum of the row distances plus the sum of the column distances, and the two can be chosen independently. On one axis the total distance is minimised at the median, and that minimum equals the sum of (largest - smallest) over pairs taken from both ends of the sorted list. A row-major scan yields the rows sorted and a column-major scan yields the columns sorted, so no sort is needed.
- Scan row by row and append r for every 1 (rows come out sorted).
- Scan column by column and append c for every 1 (columns come out sorted).
- For each list, use two pointers i = 0, j = end; while i < j add list[j] - list[i] and move both inward.
- Return the sum of the two results.
class Solution {
public int minTotalDistance(int[][] grid) {
int m = grid.length, n = grid[0].length;
List<Integer> rows = new ArrayList<>();
List<Integer> cols = new ArrayList<>();
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 1) rows.add(r);
}
}
for (int c = 0; c < n; c++) {
for (int r = 0; r < m; r++) {
if (grid[r][c] == 1) cols.add(c);
}
}
return spread(rows) + spread(cols);
}
private int spread(List<Integer> sorted) {
int total = 0;
for (int i = 0, j = sorted.size() - 1; i < j; i++, j--) {
total += sorted.get(j) - sorted.get(i);
}
return total;
}
}class Solution:
def minTotalDistance(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
rows = [r for r in range(m) for c in range(n) if grid[r][c] == 1]
cols = [c for c in range(n) for r in range(m) if grid[r][c] == 1]
def spread(values: List[int]) -> int:
total = 0
i, j = 0, len(values) - 1
while i < j:
total += values[j] - values[i]
i += 1
j -= 1
return total
return spread(rows) + spread(cols)class Solution {
public:
int minTotalDistance(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<int> rows, cols;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (grid[r][c] == 1) rows.push_back(r);
for (int c = 0; c < n; c++)
for (int r = 0; r < m; r++)
if (grid[r][c] == 1) cols.push_back(c);
return spread(rows) + spread(cols);
}
private:
int spread(const vector<int>& v) {
int total = 0;
for (int i = 0, j = (int)v.size() - 1; i < j; i++, j--) total += v[j] - v[i];
return total;
}
};function minTotalDistance(grid) {
const m = grid.length, n = grid[0].length;
const rows = [], cols = [];
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (grid[r][c] === 1) rows.push(r);
}
}
for (let c = 0; c < n; c++) {
for (let r = 0; r < m; r++) {
if (grid[r][c] === 1) cols.push(c);
}
}
const spread = (v) => {
let total = 0;
for (let i = 0, j = v.length - 1; i < j; i++, j--) total += v[j] - v[i];
return total;
};
return spread(rows) + spread(cols);
}Edge cases to test
- All homes in one row or one column
- Several homes in the same row (the row value repeats in the list)
- An even number of homes, where every point between the two middle ones is optimal
- The best meeting cell is itself a home
Hints
Hint 1
Manhattan distance splits into a row part and a column part. Can you minimise the two parts separately?
Hint 2
On a line, the point that minimises the total distance to a set of points is their median.
Hint 3
Reading the grid row by row gives the row indices already sorted; reading it column by column gives the column indices sorted. Then pair the smallest with the largest.
FAQ
What is the best time complexity for Best Meeting Point?
Optimal (median per axis) runs in O(m · n) time and O(k) extra space. Two full scans of the grid plus a linear pass over each list.
Which pattern does Best Meeting Point use?
It is a arrays & hashing problem that uses the matrix traversal pattern. Other problems with the same pattern: Spiral Matrix, Diagonal Traverse, Sparse Matrix Multiplication.
Is there a brute force solution for Best Meeting Point?
Yes. Brute force (try every cell) takes O(m · n · k) time and O(k) space. Collect all homes.
Which edge cases should I test for Best Meeting Point?
All homes in one row or one column; Several homes in the same row (the row value repeats in the list); An even number of homes, where every point between the two middle ones is optimal; The best meeting cell is itself a home.