Best Meeting Point

Problem#

Given a binary grid where 1 represents a person’s home, return the minimum total Manhattan distance from a meeting point to every home. The meeting point can be any cell.

Examples#

[[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]] → 6
[[1,1]] → 1

Constraints#

m == grid.length, n == grid[i].length, 1 <= m, n <= 200. At least one 1.

Approach#

Manhattan distance |r - rm| + |c - cm| separates additively across rows and columns. The 1D facility-location optimum is the median. Collect row indices in row-major order (naturally sorted), then column indices in column-major order to keep them sorted; sum deviations from each axis’s median.

Solution#

class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> rows, cols;
        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);
        return medianDist(rows) + medianDist(cols);
    }
private:
    int medianDist(vector<int>& v) {
        int sum = 0, l = 0, r = v.size() - 1;
        while (l < r) { sum += v[r--] - v[l++]; }
        return sum;
    }
};

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)
            }
        }
    }
    medianDist := func(v []int) int {
        sum, l, r := 0, 0, len(v)-1
        for l < r {
            sum += v[r] - v[l]
            l++
            r--
        }
        return sum
    }
    return medianDist(rows) + medianDist(cols)
}

from typing import List

class Solution:
    def minTotalDistance(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        rows: List[int] = []
        cols: List[int] = []
        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)

        def median_dist(v: List[int]) -> int:
            total, l, r = 0, 0, len(v) - 1
            while l < r:
                total += v[r] - v[l]
                l += 1
                r -= 1
            return total

        return median_dist(rows) + median_dist(cols)

var minTotalDistance = function(grid) {
    const m = grid.length, n = grid[0].length;
    const rows = [], cols = [];
    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 medianDist = (v) => {
        let sum = 0, l = 0, r = v.length - 1;
        while (l < r) {
            sum += v[r] - v[l];
            l++;
            r--;
        }
        return sum;
    };
    return medianDist(rows) + medianDist(cols);
};

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);
            }
        }
        return medianDist(rows) + medianDist(cols);
    }

    private int medianDist(List<Integer> v) {
        int sum = 0, l = 0, r = v.size() - 1;
        while (l < r) {
            sum += v.get(r) - v.get(l);
            l++;
            r--;
        }
        return sum;
    }
}

function minTotalDistance(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const rows: number[] = [], 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 medianDist = (v: number[]): number => {
        let sum = 0, l = 0, r = v.length - 1;
        while (l < r) {
            sum += v[r] - v[l];
            l++;
            r--;
        }
        return sum;
    };
    return medianDist(rows) + medianDist(cols);
}

Editorial#

For 1D points, picking the median minimizes the sum of absolute deviations. The two-pointer trick pairs the smallest with the largest, summing their span — the chosen meeting point lies anywhere between them, which is precisely the median range.

Complexity#

Time: O(m*n).
Space: O(m + n).

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#