Coding

Best Meeting Point

Asked atLLinkeye

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an m x n binary grid grid where each 1 marks the home of one friend, return the minimal total travel distance. The total travel distance is the sum of the distances between the houses of the friends and the meeting point. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Input: grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]] Output: 6 Explanation: Given three friends living at (0,0), (0,4), and (2,2). The point (0,2) is an ideal meeting point, as the total travel distance of 2 + 2 + 2 = 6 is minimal. So return 6.

**Input: **grid = [[1,1]] **Output: **1

**Input: **grid = [[0,1],[1,0],[0,1]]

m == grid.length
n == grid[i].length
1 <= m, n <= 200
grid[i][j] is either 0 or 1.
There will be at least two friends in the grid.

cpp

class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
        // User code goes here
    }
};

java

class Solution {
    public int minTotalDistance(int[][] grid) {
        // User code goes here
    }
}

python

class Solution:
    def minTotalDistance(self, grid):
        # User code goes here

javascript

class Solution {
    minTotalDistance(grid) {
        // User code goes here
    }
}

csharp

public class Solution
{
    public int MinTotalDistance(int[][] grid)
    {
        // User code goes here
    }
}

func minTotalDistance(grid [][]int) int {

}

Stuck? Show a way to structure it+

01Collect row and column positions for every person
02Find the median coordinate in each dimension
03Sum absolute row and column distances
04Explain separability of Manhattan distance

Reference answer

Start by restating the input contract for Best Meeting Point and testing the smallest boundary case before choosing the algorithm. For people on a grid using Manhattan distance, choose the median row and median column independently. Collect all occupied row indices and column indices, take their medians, then sum absolute differences from every person to those coordinates. Explain the invariant while coding, then show how each update preserves it. For an R by C grid with P people, collection plus sorting costs O(R * C + P log P) time and the coordinate lists use O(P) space. Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

Then expect these follow-ups

What if each person has a weight?
Tests: follow-up reasoning
How can sorted traversal avoid sorting rows?
Tests: follow-up reasoning

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question