Skip to main content
Talentd

Best Meeting Point - Solution & Explanation

HardPremiumFree on FleetCodeArrayMathSortingMatrix5 min readAsked at: Amazon, Microsoft, Meta +6
Practice this problem

Problem Statement

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|.

 

Example 1:

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.

Example 2:

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

 

Constraints:

  • 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.

Approach Overview

Problem Overview: You’re given a binary grid where 1 represents a person's home. The goal is to choose a meeting cell that minimizes the sum of Manhattan distances from all homes to that point. Movement is allowed only horizontally and vertically, so the Manhattan metric drives the optimal strategy.

Approach 1: Brute Force – Try Every Cell (O((mn)^2) time, O(1) space)

Enumerate every cell in the matrix as a potential meeting point. For each candidate cell, iterate through the grid again and compute the Manhattan distance to every home using |r1 - r2| + |c1 - c2|. Track the minimum total distance seen so far. This approach is straightforward but expensive because for each of the m * n cells you scan the entire grid again. It works for small grids and demonstrates the distance calculation logic, but it quickly becomes impractical for large inputs.

Approach 2: Median with Sorting (O(mn log mn) time, O(mn) space)

Manhattan distance separates cleanly into row distance and column distance. That means you can minimize them independently. Collect the row indices and column indices of every home into two arrays. After collecting them, sort both arrays using a typical sorting algorithm. The optimal meeting coordinate is the median of the rows and the median of the columns. This works because the median minimizes the sum of absolute differences, a core property used in many math optimization problems. Compute the total distance by summing the absolute difference between each coordinate and the chosen median.

Approach 3: Median without Sorting (O(mn) time, O(mn) space)

You can avoid sorting entirely by exploiting grid traversal order. Scan the grid row-by-row and append row indices when you encounter a home. This automatically keeps rows sorted. Then scan column-by-column and append column indices, which keeps the column list sorted as well. With both arrays already ordered, the median element can be accessed directly. Finally compute the total Manhattan distance from all rows to the row median and from all columns to the column median. This reduces the time complexity to linear in the number of cells while preserving the same optimal meeting point.

Recommended for interviews: The median-based approach is the expected solution. Start by explaining the brute force to show understanding of Manhattan distance, then pivot to the insight that distance splits into row and column components. Identifying the median as the minimizer of absolute differences demonstrates strong algorithmic reasoning and familiarity with grid problems.

Solution

Code

PythonJavaC++GoRust

Python

Java

C++

Go

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force (Check Every Cell)O((mn)^2)O(1)Good for explaining the Manhattan distance idea or validating correctness on small grids
Median with SortingO(mn log mn)O(mn)General solution when collecting coordinates then sorting is simplest to implement
Median without SortingO(mn)O(mn)Optimal approach when you leverage grid traversal order to keep coordinates sorted

Video Solution

Best Meeting Point | Leetcode 296 Solution in Hindi • Pepcoding • 11,361 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Best Meeting Point easy or hard?
Best Meeting Point is classified as Hard on LeetCode because the key insight about medians is not obvious at first. Once you recognize that Manhattan distance separates into independent row and column components, the implementation becomes relatively straightforward.
Best Meeting Point Python/Java solution
Python and Java solutions typically collect row and column indices into lists, compute the median element, and sum absolute distances to that median. The logic is identical across languages: iterate through the grid, build coordinate arrays, determine medians, and compute total Manhattan distance.
How to solve Best Meeting Point in O(n)?
Treat row and column distances independently. Traverse the grid to collect all row indices and column indices of homes. Because traversal order keeps them sorted, the median element of each list is the optimal coordinate. Summing absolute differences from all rows to the row median and all columns to the column median gives the minimal total distance in O(mn) time.
What is the best approach for Best Meeting Point?
The optimal approach uses the median of home coordinates. Collect all row indices and column indices of homes, then choose the median row and median column as the meeting point. The median minimizes the sum of absolute differences, which directly minimizes Manhattan distance. This yields an O(mn) or O(mn log mn) solution depending on whether sorting is needed.
Is Best Meeting Point asked at Google/Amazon/Meta?
Best Meeting Point has appeared in interviews at companies that emphasize algorithmic grid problems, including Google and Meta-style interview rounds. It tests understanding of Manhattan distance, median properties, and grid traversal optimization.
What data structure is used in Best Meeting Point?
The solution primarily uses arrays or lists to store row and column indices of homes. After collecting coordinates, the algorithm relies on median selection and simple absolute difference calculations rather than complex data structures.
What is the time complexity of Best Meeting Point?
The optimal implementation runs in O(mn) time where m and n are grid dimensions. By collecting row indices in row order and column indices in column order, both arrays are naturally sorted and the median can be accessed directly. A simpler implementation that sorts the coordinate arrays runs in O(mn log mn).

Ready to solve this problem?

Practice Best Meeting Point with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Moves to Equal Array Elements II

Next

Shortest Distance from All Buildings