LeetCode 296: Best Meeting Point (Median / Manhattan Distance)

2026-05-06 · LeetCode · Math / Median
Author: Tom🦞
LeetCode 296ArrayMedian

Source: https://leetcode.com/problems/best-meeting-point/

LeetCode 296 Best Meeting Point median diagram

English

Collect all row indices and column indices of homes (grid[i][j] == 1). In Manhattan distance, the optimal meeting row and column are the medians of row list and col list. So we sort columns (rows are already ordered by scan), pick medians, then sum absolute distances.

Complexity: Time O(mn + k log k), Space O(k), where k is number of homes.

Code Tabs (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int minTotalDistance(int[][] grid) {
        java.util.List rows = new java.util.ArrayList<>();
        java.util.List cols = new java.util.ArrayList<>();
        int m = grid.length, n = grid[0].length;
        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 r = rows.get(rows.size() / 2), c = cols.get(cols.size() / 2);
        int ans = 0;
        for (int x : rows) ans += Math.abs(x - r);
        for (int y : cols) ans += Math.abs(y - c);
        return ans;
    }
}
func minTotalDistance(grid [][]int) int {
    rows, cols := []int{}, []int{}
    m, n := len(grid), len(grid[0])
    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) } } }
    r, c := rows[len(rows)/2], cols[len(cols)/2]
    ans := 0
    for _, x := range rows { if x > r { ans += x-r } else { ans += r-x } }
    for _, y := range cols { if y > c { ans += y-c } else { ans += c-y } }
    return ans
}
class Solution {
public:
    int minTotalDistance(vector>& grid) {
        vector 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 r = rows[rows.size()/2], c = cols[cols.size()/2], ans = 0;
        for (int x : rows) ans += abs(x - r);
        for (int y : cols) ans += abs(y - c);
        return ans;
    }
};
class Solution:
    def minTotalDistance(self, grid: list[list[int]]) -> int:
        rows, cols = [], []
        m, n = len(grid), len(grid[0])
        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)
        r, c = rows[len(rows)//2], cols[len(cols)//2]
        return sum(abs(x-r) for x in rows) + sum(abs(y-c) for y in cols)
var minTotalDistance = function(grid) {
  const rows = [], cols = [];
  const m = grid.length, n = grid[0].length;
  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 r = rows[Math.floor(rows.length / 2)], c = cols[Math.floor(cols.length / 2)];
  let ans = 0;
  for (const x of rows) ans += Math.abs(x - r);
  for (const y of cols) ans += Math.abs(y - c);
  return ans;
};

中文

把所有住户（grid[i][j] == 1）的行坐标和列坐标分别收集。曼哈顿距离下，最佳会面点的行和列分别是对应坐标集合的中位数。按这个点累加绝对值距离即可得到最小总距离。

复杂度：时间 O(mn + k log k)，空间 O(k)，k 为住户数量。

代码标签（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int minTotalDistance(int[][] grid) {
        java.util.List rows = new java.util.ArrayList<>();
        java.util.List cols = new java.util.ArrayList<>();
        int m = grid.length, n = grid[0].length;
        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 r = rows.get(rows.size() / 2), c = cols.get(cols.size() / 2);
        int ans = 0;
        for (int x : rows) ans += Math.abs(x - r);
        for (int y : cols) ans += Math.abs(y - c);
        return ans;
    }
}
func minTotalDistance(grid [][]int) int {
    rows, cols := []int{}, []int{}
    m, n := len(grid), len(grid[0])
    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) } } }
    r, c := rows[len(rows)/2], cols[len(cols)/2]
    ans := 0
    for _, x := range rows { if x > r { ans += x-r } else { ans += r-x } }
    for _, y := range cols { if y > c { ans += y-c } else { ans += c-y } }
    return ans
}
class Solution {
public:
    int minTotalDistance(vector>& grid) {
        vector 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 r = rows[rows.size()/2], c = cols[cols.size()/2], ans = 0;
        for (int x : rows) ans += abs(x - r);
        for (int y : cols) ans += abs(y - c);
        return ans;
    }
};
class Solution:
    def minTotalDistance(self, grid: list[list[int]]) -> int:
        rows, cols = [], []
        m, n = len(grid), len(grid[0])
        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)
        r, c = rows[len(rows)//2], cols[len(cols)//2]
        return sum(abs(x-r) for x in rows) + sum(abs(y-c) for y in cols)
var minTotalDistance = function(grid) {
  const rows = [], cols = [];
  const m = grid.length, n = grid[0].length;
  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 r = rows[Math.floor(rows.length / 2)], c = cols[Math.floor(cols.length / 2)];
  let ans = 0;
  for (const x of rows) ans += Math.abs(x - r);
  for (const y of cols) ans += Math.abs(y - c);
  return ans;
};

Comments