Best Meeting Point

hard math median matrix

Problem

Given an m×n grid where 1 marks a home, find the point where the total Manhattan distance from every home is minimized.

Inputgrid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]

Output6

Median row = 0, median col = 2 — total |0-0|+|0-0|+|2-0|+|0-2|+|0-2|+|2-2|=6.

grid (rows by ';', cells by ',')

def min_total_distance(grid):
    rows, cols = [], []
    for r, row in enumerate(grid):
        for c, v in enumerate(row):
            if v == 1:
                rows.append(r); cols.append(c)
    cols.sort()
    mr, mc = rows[len(rows)//2], cols[len(cols)//2]
    return sum(abs(r - mr) for r in rows) + sum(abs(c - mc) for c in cols)

function minTotalDistance(grid) {
  const rows = [], cols = [];
  for (let r = 0; r < grid.length; r++)
    for (let c = 0; c < grid[0].length; c++)
      if (grid[r][c] === 1) { rows.push(r); cols.push(c); }
  cols.sort((a, b) => a - b);
  const mr = rows[Math.floor(rows.length / 2)];
  const mc = cols[Math.floor(cols.length / 2)];
  let total = 0;
  rows.forEach(r => total += Math.abs(r - mr));
  cols.forEach(c => total += Math.abs(c - mc));
  return total;
}

class Solution {
    public int minTotalDistance(int[][] grid) {
        List rows = new ArrayList<>(), cols = new ArrayList<>();
        for (int r = 0; r < grid.length; r++)
            for (int c = 0; c < grid[0].length; c++)
                if (grid[r][c] == 1) { rows.add(r); cols.add(c); }
        Collections.sort(cols);
        int mr = rows.get(rows.size() / 2);
        int mc = cols.get(cols.size() / 2);
        int total = 0;
        for (int r : rows) total += Math.abs(r - mr);
        for (int c : cols) total += Math.abs(c - mc);
        return total;
    }
}

int minTotalDistance(vector>& grid) {
    vector rows, cols;
    for (int r = 0; r < (int)grid.size(); r++)
        for (int c = 0; c < (int)grid[0].size(); c++)
            if (grid[r][c] == 1) { rows.push_back(r); cols.push_back(c); }
    sort(cols.begin(), cols.end());
    int mr = rows[rows.size() / 2], mc = cols[cols.size() / 2];
    int total = 0;
    for (int r : rows) total += abs(r - mr);
    for (int c : cols) total += abs(c - mc);
    return total;
}

Explanation

The big insight is that Manhattan distance splits cleanly into two independent problems: the horizontal part (columns) and the vertical part (rows). So we can pick the best row and the best column completely separately, then add the two costs.

For a single line of points, the spot that minimizes total distance is the median. That is why we collect all the row indices of the homes into rows and all the column indices into cols, then grab the middle element of each as the meeting point.

Once we have the median row mr and median column mc, the answer is simply the sum of abs(r - mr) over every home's row plus abs(c - mc) over every home's column.

Example: homes sit at rows [0, 0, 2] and columns [0, 4, 2]. Sorted columns are [0, 2, 4], so the medians are mr = 0 and mc = 2. Row cost is 0+0+2 = 2 and column cost is 2+0+2 = 4, giving 6.

Notice rows is already sorted because we scan the grid top to bottom, so only cols needs an explicit sort. Choosing the median (not the average) is what guarantees the smallest total walking distance.

Time: O(mn) Space: O(mn)