Closest Meeting Point

Given N people on an MxM grid, find the point that requires the minimum total distance travelled by all N people to meet at that point.

Statement

There is an MxM grid where N people live. These N people want to meet such that the total travel distance is minimized. The travel distance is to be calculated using the Euclidean distance metric. For two points on this grid, (x​1,y​1) and (x​2, y2), the Euclidean distance between them is given by:

d=(x2x1)2+(y2y1)2d=\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}

We use Euclidean distance here because the people on the grid can move diagonally as well.

Note: We cannot use Manhattan distance (d=x2x1+y2y1d = |x_2-x_1| + |y_2-y_1|) here because it is a measure of the horizontal and vertical distance and does not cover the diagonal distance.

Example

Consider a 5x5 grid with 3 people, located at:

A (1, 2), B (3, 3), and C (4, 2).

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.