# 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:

```python
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

| Item | Meaning |
|---|---|
| Input | 2D grid of `0` and `1` |
| Output | Minimum total Manhattan distance |
| `1` | A person's home |
| `0` | Empty cell |
| Meeting point | Any grid cell |

Function shape:

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

## Examples

For:

```python
grid = [
    [1, 0, 0, 0, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0],
]
```

The people live at:

```python
(0, 0)
(0, 4)
(2, 2)
```

A best meeting point is:

```python
(0, 2)
```

The total distance is:

```python
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:

```python
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:

```python
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:

```python
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:

```python
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:

```python
median row, median column
```

For the example:

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

Sorted columns:

```python
[0, 2, 4]
```

Median row is `0`.

Median column is `2`.

So a best meeting point is:

```python
(0, 2)
```

## Why the Median Works

Consider points on a line:

```python
x1 <= x2 <= x3 <= ... <= xk
```

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

```python
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:

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

Finally, compute:

```python
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:

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

| Metric | Value | Why |
|---|---|---|
| Time | `O(R * C + P)` | Scan the grid and sum distances |
| Space | `O(P)` | Store row and column coordinates |

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

## Implementation

```python
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:

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

Then we collect home rows:

```python
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:

```python
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:

```python
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:

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

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

Finally:

```python
return distance
```

returns the minimum total travel distance.

## Testing

```python
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:

| Test | Why |
|---|---|
| Standard example | Confirms expected answer `6` |
| One row | Reduces to 1D column median |
| One column | Reduces to 1D row median |
| Diagonal homes | Checks row and column separation |
| Multiple homes in one row | Checks median column behavior |