Find Perfect Location: Find the Optimal Meeting Point on a 2D Map

Question

## Problem

Given `n` people at positions on a 2D grid, find the location that minimizes the **total travel distance** (Manhattan distance) for all of them to meet. The meeting point does not need to be at an existing person's location.

```python
def find_meeting_point(positions: list[tuple[int, int]]) -> tuple[int, int]:
    pass
```

## Example

```
Input: positions = [(0, 0), (2, 2), (4, 0)]

For Manhattan distance, the optimal x is the median of x-coords,
and the optimal y is the median of y-coords.

Median x = 2, median y = 0
Output: (2, 0)

Total distance: |0-2|+|0-0| + |2-2|+|2-0| + |4-2|+|0-0| = 2+2+2 = 6
```

## Follow-ups

1. Prove why the median minimizes total Manhattan distance (vs. mean, which minimizes L2).
2. If people have different weights (e.g., some need to travel multiple times), how does the solution change?
3. How do you solve the Euclidean (L2) version — is there a closed-form solution?
4. What if the meeting point must be on an existing road network (graph), not a free grid?

Find Perfect Location: Find the Optimal Meeting Point on a 2D Map

Question Details

Full Details

Topics

More from Reddit