LeetCode 296: Best Meeting Point

Problem Restatement

We are given a 2D grid containing only 0 and 1.

Each 1 marks the home of one person.

A group of people wants to meet at one grid cell while minimizing the total travel distance.

Distance is measured by Manhattan distance:

distance = abs(r1 - r2) + abs(c1 - c2)

We need to return the minimum possible total distance.

The source statement says there are two or more people, each 1 marks a home, and distance is calculated using Manhattan distance. The example has people at (0, 0), (0, 4), and (2, 2), with minimum total distance 6.

Input and Output

Function shape:

class Solution:
    def minTotalDistance(self, grid: list[list[int]]) -> int:
        ...

Examples

For:

grid = [
    [1, 0, 0, 0, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0],
]

The people live at:

(0, 0)
(0, 4)
(2, 2)

A best meeting point is:

(0, 2)

The total distance is:

abs(0 - 0) + abs(0 - 2) = 2
abs(0 - 0) + abs(4 - 2) = 2
abs(2 - 0) + abs(2 - 2) = 2

So the answer is:

6

First Thought: Try Every Cell

A direct solution is to test every cell as the meeting point.

For each cell (r, c):

1. Compute its distance to every home.
2. Add those distances.
3. Keep the minimum total.

Code idea:

answer = float("inf")

for r in range(rows):
    for c in range(cols):
        total = 0

        for home_r, home_c in homes:
            total += abs(home_r - r) + abs(home_c - c)

        answer = min(answer, total)

This is correct, but slow.

If the grid has R rows, C columns, and P people, this costs:

O(R * C * P)

We can do better by using the structure of Manhattan distance.

Key Insight

Manhattan distance separates into row distance and column distance.

For a meeting point (r, c), the total distance is:

sum(abs(home_r - r)) + sum(abs(home_c - c))

The row choice and column choice are independent.

So the 2D problem becomes two 1D problems:

1. Choose the best row.
2. Choose the best column.

In one dimension, the point that minimizes the sum of absolute distances is the median.

So we should meet at:

median row, median column

For the example:

rows = [0, 0, 2]
cols = [0, 4, 2]

Sorted columns:

[0, 2, 4]

Median row is 0.

Median column is 2.

So a best meeting point is:

(0, 2)

Why the Median Works

Consider points on a line:

x1 <= x2 <= x3 <= ... <= xk

If we choose a meeting coordinate x, the total distance is:

abs(x1 - x) + abs(x2 - x) + ... + abs(xk - x)

Moving x toward the median decreases distance to at least as many points as it increases.

Moving away from the median increases distance to more points than it helps.

Therefore any median minimizes the sum of absolute distances.

For an odd number of points, the median is the middle point.

For an even number of points, any coordinate between the two middle points gives the same minimum.

Algorithm

Collect all row indices where grid[r][c] == 1.

Collect all column indices where grid[r][c] == 1.

Rows can be collected in sorted order by scanning row by row.

Columns can be collected in sorted order by scanning column by column.

Then choose:

median_row = rows[len(rows) // 2]
median_col = cols[len(cols) // 2]

Finally, compute:

sum(abs(row - median_row) for row in rows)
+
sum(abs(col - median_col) for col in cols)

Return that sum.

Correctness

For any meeting point (r, c), the total Manhattan distance equals the sum of all row distances plus the sum of all column distances.

The choice of r affects only row distances, and the choice of c affects only column distances.

In one dimension, the median minimizes the sum of absolute distances. Therefore choosing the median row minimizes the row part, and choosing the median column minimizes the column part.

Since the two parts are independent, combining these two optimal choices gives a meeting point with minimum total Manhattan distance.

The algorithm computes exactly this value. Therefore it returns the minimum possible total distance.

Complexity

Let:

R = number of rows
C = number of columns
P = number of people

This implementation avoids sorting by collecting rows and columns in sorted order.

Implementation

class Solution:
    def minTotalDistance(self, grid: list[list[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        home_rows = []
        home_cols = []

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    home_rows.append(r)

        for c in range(cols):
            for r in range(rows):
                if grid[r][c] == 1:
                    home_cols.append(c)

        median_row = home_rows[len(home_rows) // 2]
        median_col = home_cols[len(home_cols) // 2]

        distance = 0

        for r in home_rows:
            distance += abs(r - median_row)

        for c in home_cols:
            distance += abs(c - median_col)

        return distance

Code Explanation

We store the grid size:

rows = len(grid)
cols = len(grid[0])

Then we collect home rows:

for r in range(rows):
    for c in range(cols):
        if grid[r][c] == 1:
            home_rows.append(r)

Because we scan from top to bottom, home_rows is already sorted.

Then we collect home columns:

for c in range(cols):
    for r in range(rows):
        if grid[r][c] == 1:
            home_cols.append(c)

Because we scan from left to right by column, home_cols is already sorted.

The median coordinates are:

median_row = home_rows[len(home_rows) // 2]
median_col = home_cols[len(home_cols) // 2]

Then we sum row distances and column distances separately:

for r in home_rows:
    distance += abs(r - median_row)

for c in home_cols:
    distance += abs(c - median_col)

Finally:

return distance

returns the minimum total travel distance.

Testing

def test_min_total_distance():
    s = Solution()

    grid = [
        [1, 0, 0, 0, 1],
        [0, 0, 0, 0, 0],
        [0, 0, 1, 0, 0],
    ]
    assert s.minTotalDistance(grid) == 6

    grid = [
        [1, 1],
    ]
    assert s.minTotalDistance(grid) == 1

    grid = [
        [1],
        [0],
        [1],
    ]
    assert s.minTotalDistance(grid) == 2

    grid = [
        [1, 0],
        [0, 1],
    ]
    assert s.minTotalDistance(grid) == 2

    grid = [
        [1, 0, 1, 0, 1],
    ]
    assert s.minTotalDistance(grid) == 4

    print("all tests passed")

test_min_total_distance()

Test meaning: