Best Meeting Point
Problem
A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.
Examples
Example 1
Input:
grid = [
[1,0,0,0,1],
[0,0,0,0,0],
[0,0,1,0,0]
]
Output:
6
Explanation: Visualize the input like grid below. We are given three people living at (0, 0), (0, 4), and (2, 2):
1 - 0 - 0 - 0 - 1
| | | | |
0 - 0 - 0 - 0 - 0
| | | | |
0 - 0 - 1 - 0 - 0
The point (0, 2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.
Solution
Method 1 – Find the Median (1D and 2D Intuition)
Intuition
The optimal meeting point to minimize the total Manhattan distance is at the median of the people's coordinates. This is because, in 1D, the sum of absolute differences is minimized at the median.
Let's visualize this in 1D:
______A_____P_______B_______
If two people live at A and B, any meeting point P between A and B gives the same total distance: |A-P| + |B-P| = |B-A|. If P is outside [A, B], the total distance increases.
Now, with more people (C, A, B, D):
______C_____A_____P_______B______D______
The best meeting point P is between the inner points (A and B), and the total distance is minimized by pairing the outermost points (C with D, A with B, etc.) and summing their distances to the median.
Approach
- Collect all row and column indices where people live (grid[i][j] == 1).
- Sort the row and column lists.
- Find the median row and median column.
- Sum the distances from each person's home to the median row and column.
- This is equivalent to minimizing the total Manhattan distance in 2D, since the Manhattan distance is separable into x and y components.
In 2D, the same principle applies: the best meeting point is at (median row, median column). The ASCII grid below shows the example:
1 - 0 - 0 - 0 - 1
| | | | |
0 - 0 - 0 - 0 - 0
| | | | |
0 - 0 - 1 - 0 - 0
The best meeting point is at (0, 2), the median of the x and y coordinates, with a minimal total distance of 6.
Code
C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int minTotalDistance(vector<vector<int>>& grid) {
vector<int> rows, cols;
int m = grid.size(), n = grid[0].size();
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 1) rows.push_back(i);
for (int j = 0; j < n; ++j)
for (int i = 0; i < m; ++i)
if (grid[i][j] == 1) cols.push_back(j);
int rowMedian = rows[rows.size() / 2];
int colMedian = cols[cols.size() / 2];
int sum = 0;
for (int r : rows) sum += abs(r - rowMedian);
for (int c : cols) sum += abs(c - colMedian);
return sum;
}
};
Go
import "sort"
func minTotalDistance(grid [][]int) int {
m, n := len(grid), len(grid[0])
rows, cols := []int{}, []int{}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 {
rows = append(rows, i)
}
}
}
for j := 0; j < n; j++ {
for i := 0; i < m; i++ {
if grid[i][j] == 1 {
cols = append(cols, j)
}
}
}
rowMedian := rows[len(rows)/2]
colMedian := cols[len(cols)/2]
sum := 0
for _, r := range rows {
sum += abs(r - rowMedian)
}
for _, c := range cols {
sum += abs(c - colMedian)
}
return sum
}
func abs(x int) int { if x < 0 { return -x }; return x }
Java
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 i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1) rows.add(i);
for (int j = 0; j < n; j++)
for (int i = 0; i < m; i++)
if (grid[i][j] == 1) cols.add(j);
int rowMedian = rows.get(rows.size() / 2);
int colMedian = cols.get(cols.size() / 2);
int sum = 0;
for (int r : rows) sum += Math.abs(r - rowMedian);
for (int c : cols) sum += Math.abs(c - colMedian);
return sum;
}
}
Kotlin
class Solution {
fun minTotalDistance(grid: Array<IntArray>): Int {
val m = grid.size
val n = grid[0].size
val rows = mutableListOf<Int>()
val cols = mutableListOf<Int>()
for (i in 0 until m)
for (j in 0 until n)
if (grid[i][j] == 1) rows.add(i)
for (j in 0 until n)
for (i in 0 until m)
if (grid[i][j] == 1) cols.add(j)
val rowMedian = rows[rows.size / 2]
val colMedian = cols[cols.size / 2]
var sum = 0
for (r in rows) sum += kotlin.math.abs(r - rowMedian)
for (c in cols) sum += kotlin.math.abs(c - colMedian)
return sum
}
}
Python
class Solution:
def minTotalDistance(self, grid: list[list[int]]) -> int:
m, n = len(grid), len(grid[0])
rows, cols = [], []
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
rows.append(i)
for j in range(n):
for i in range(m):
if grid[i][j] == 1:
cols.append(j)
row_median = rows[len(rows)//2]
col_median = cols[len(cols)//2]
return sum(abs(r - row_median) for r in rows) + sum(abs(c - col_median) for c in cols)
Rust
impl Solution {
pub fn min_total_distance(grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
let mut rows = Vec::new();
let mut cols = Vec::new();
for i in 0..m {
for j in 0..n {
if grid[i][j] == 1 {
rows.push(i as i32);
}
}
}
for j in 0..n {
for i in 0..m {
if grid[i][j] == 1 {
cols.push(j as i32);
}
}
}
let row_median = rows[rows.len() / 2];
let col_median = cols[cols.len() / 2];
rows.iter().map(|&r| (r - row_median).abs()).sum::<i32>() +
cols.iter().map(|&c| (c - col_median).abs()).sum::<i32>()
}
}
TypeScript
class Solution {
minTotalDistance(grid: number[][]): number {
const m = grid.length, n = grid[0].length;
const rows: number[] = [];
const cols: number[] = [];
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
if (grid[i][j] === 1) rows.push(i);
for (let j = 0; j < n; j++)
for (let i = 0; i < m; i++)
if (grid[i][j] === 1) cols.push(j);
const rowMedian = rows[Math.floor(rows.length / 2)];
const colMedian = cols[Math.floor(cols.length / 2)];
let sum = 0;
for (const r of rows) sum += Math.abs(r - rowMedian);
for (const c of cols) sum += Math.abs(c - colMedian);
return sum;
}
}
Complexity
- ⏰ Time complexity:
O(mn + k log k), wheremandnare the grid dimensions andkis the number of people (1s in the grid). Collecting coordinates isO(mn), and sorting isO(k log k). - 🧺 Space complexity:
O(k), for storing the row and column indices.