Best Meeting Point

Best Meeting Point looks like a 2-D grid puzzle, but it hides a one-line math fact: on a line, the point that minimizes total distance to a set of points is their median. Manhattan distance lets us solve the two axes completely independently.

The slow way first

The brute-force idea is to try every cell as the meeting point, and for each one sum the distance to all homes. That is O(m·n) candidate cells times O(homes) work each — far too slow on a large grid, and it completely misses the structure of the problem.

The question to ask: can the two coordinates be chosen separately? Because Manhattan distance splits into a row part plus a column part, the answer is yes — and that changes everything.

The idea: median on each axis

Total distance is sum(|r - mr|) + sum(|c - mc|). The first sum only depends on the meeting row mr; the second only on the meeting column mc. So we can minimize each independently. On a 1-D line, the value that minimizes the sum of absolute distances is the median of the points.

So: collect the sorted list of home rows and the sorted list of home columns, take the median of each, and the meeting point is (median row, median column).

A neat trick keeps both lists sorted for free: scan rows top-to-bottom to collect row indices, and scan columns left-to-right to collect column indices. No explicit sort needed.

Walk through it

Step through the animation. First we gather the row coordinates [0, 0, 2] and the column coordinates [0, 2, 4]. The median row is 0 and the median column is 2, so the highlighted cross marks the meeting point (0, 2). Summing the absolute gaps gives 2 + 4 = 6.

Pseudocode

rows = []                       # collect row index of every home
cols = []
for each cell (r, c) scanned row by row:
    if cell is a home: rows.append(r)     # rows ends up sorted
for each cell (r, c) scanned column by column:
    if cell is a home: cols.append(c)     # cols ends up sorted
mr = rows[len(rows) // 2]        # median row
mc = cols[len(cols) // 2]        # median col
return sum(|r - mr|) + sum(|c - mc|)

The Python solution

def min_total_distance(grid):
    rows = []
    cols = []
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == 1:
                rows.append(r)
    for c in range(len(grid[0])):
        for r in range(len(grid)):
            if grid[r][c] == 1:
                cols.append(c)
    # both lists arrive sorted by scan order
    med_r = rows[len(rows) // 2]
    med_c = cols[len(cols) // 2]
    dist = sum(abs(r - med_r) for r in rows)
    dist += sum(abs(c - med_c) for c in cols)
    return dist

• The first double loop scans row by row, so rows comes out non-decreasing automatically.
• The second double loop scans column by column, so cols comes out sorted too.
• med_r and med_c (lines 13-14) are the medians — the 1-D minimizers for each axis.
• The two sum(abs(...)) lines add the row distance and the column distance independently.
• Because the lists are already sorted, picking the middle element is the median in O(1).

Complexity

We do two linear passes over the grid to collect coordinates, then O(1) median lookups. Space is O(h) for the two coordinate lists.

When this pattern shows up

Practice