LeetCode 296 - Best Meeting Point

The problem gives us a two-dimensional binary grid where each cell contains either 0 or 1. A value of 1 represents the home location of a friend, while 0 represents an empty cell.

leetcodehardarraymathsortingmatrix

LeetCode Problem 296

Difficulty: 🔴 Hard
Topics: Array, Math, Sorting, Matrix

Solution

Problem Understanding

The problem gives us a two-dimensional binary grid where each cell contains either 0 or 1. A value of 1 represents the home location of a friend, while 0 represents an empty cell. We must choose a single meeting point somewhere in the grid such that the sum of all Manhattan distances from every friend's home to that meeting point is as small as possible.

The Manhattan distance between two points (x1, y1) and (x2, y2) is defined as:

$|x_2 - x_1| + |y_2 - y_1|$

Unlike Euclidean distance, Manhattan distance measures movement only along rows and columns, which makes it particularly suitable for grid-based movement.

The key observation is that the total distance can be separated into two independent problems:

  • Minimize vertical movement
  • Minimize horizontal movement

Suppose the meeting point is (r, c). Then the total distance becomes:

$\sum |r_i-r| + \sum |c_i-c|$

This separability is extremely important because it allows us to solve the row and column dimensions independently.

The constraints tell us that both dimensions are at most 200, so the total number of cells is at most 40,000. This is small enough for linear or near-linear solutions, but large enough that expensive brute-force computations can become inefficient.

There are several important edge cases to keep in mind. Multiple friends may already live on the same row or same column. The optimal meeting point may not correspond to an existing friend's location. The grid may contain only a few friends, or nearly every cell may contain a friend. Since the problem guarantees at least two friends, we never need to handle an empty set of homes.

Approaches

Brute Force Approach

A straightforward solution is to try every possible grid cell as the meeting point.

For each candidate cell (r, c), we compute the Manhattan distance from every friend's home to that location and sum all distances. After evaluating all possible meeting points, we return the minimum total distance found.

This approach is correct because it exhaustively checks every valid answer. No possible meeting point is skipped, so the minimal distance must eventually be discovered.

However, the performance is poor. If the grid contains m * n cells and there are k friends, then for every candidate meeting point we compute distances to all friends. The total complexity becomes:

$O(mnk)$

In the worst case, where nearly every cell contains a friend, this can approach:

$O(m^2n^2)$

While this may still pass for small grids, it is unnecessarily expensive.

Optimal Approach

The optimal solution relies on a mathematical property of Manhattan distance.

For a one-dimensional set of points, the location minimizing the sum of absolute distances is the median.

For example, given positions [1, 2, 10], choosing 2 minimizes:

  • |1 - x| + |2 - x| + |10 - x|

This same principle applies independently to rows and columns.

Therefore:

  • The optimal row is the median of all friend row indices
  • The optimal column is the median of all friend column indices

Once we know the medians, we simply compute the total distance from all friends to those coordinates.

An important implementation detail is that rows can be collected in sorted order naturally by scanning row by row, and columns can also be collected in sorted order by scanning column by column. This avoids needing an explicit sort.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(mnk) O(k) Tries every grid cell as a meeting point
Optimal O(mn) O(k) Uses the median property of Manhattan distance

Algorithm Walkthrough

  1. Traverse the grid row by row and collect the row indices of every friend into a list called rows.

We scan top to bottom, so the row indices are automatically sorted. This matters because the median requires ordered values. 2. Traverse the grid column by column and collect the column indices of every friend into a list called cols.

We scan left to right, so the column indices are also automatically sorted. 3. Find the median row.

Since rows is already sorted, the median is simply:

rows[len(rows) // 2]

The median minimizes the sum of absolute vertical distances. 4. Find the median column.

Similarly:

cols[len(cols) // 2]

This minimizes the sum of absolute horizontal distances. 5. Compute the total distance.

For every row index in rows, add its distance to the median row.

For every column index in cols, add its distance to the median column. 6. Return the combined total.

Since Manhattan distance is separable into row and column components, adding the two totals gives the minimal overall travel distance.

Why it works

The correctness comes from a classic mathematical property: in one dimension, the median minimizes the sum of absolute deviations.

Because Manhattan distance can be decomposed into independent row and column distances, minimizing each dimension separately also minimizes the combined distance. Therefore, choosing the median row and median column guarantees the globally optimal meeting point.

Python Solution

from typing import List

class Solution:
    def minTotalDistance(self, grid: List[List[int]]) -> int:
        rows = []
        cols = []

        m = len(grid)
        n = len(grid[0])

        # Collect row indices in sorted order
        for r in range(m):
            for c in range(n):
                if grid[r][c] == 1:
                    rows.append(r)

        # Collect column indices in sorted order
        for c in range(n):
            for r in range(m):
                if grid[r][c] == 1:
                    cols.append(c)

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

        total_distance = 0

        for row in rows:
            total_distance += abs(row - median_row)

        for col in cols:
            total_distance += abs(col - median_col)

        return total_distance

The implementation begins by collecting all friend row positions into the rows list. Because the grid is scanned row by row, the resulting list is already sorted.

Next, the code collects all friend column positions into cols. By scanning column by column, this list is also naturally sorted.

The median row and median column are then selected using integer division. For an even number of elements, either middle value works correctly because any point between the two medians minimizes the total absolute distance.

The final loops compute the sum of distances from every friend to the chosen median coordinates. Since the row and column distances are independent, their sums can simply be added together.

Go Solution

package main

import "math"

func minTotalDistance(grid [][]int) int {
	rows := []int{}
	cols := []int{}

	m := len(grid)
	n := len(grid[0])

	// Collect rows in sorted order
	for r := 0; r < m; r++ {
		for c := 0; c < n; c++ {
			if grid[r][c] == 1 {
				rows = append(rows, r)
			}
		}
	}

	// Collect cols in sorted order
	for c := 0; c < n; c++ {
		for r := 0; r < m; r++ {
			if grid[r][c] == 1 {
				cols = append(cols, c)
			}
		}
	}

	medianRow := rows[len(rows)/2]
	medianCol := cols[len(cols)/2]

	totalDistance := 0

	for _, row := range rows {
		totalDistance += int(math.Abs(float64(row - medianRow)))
	}

	for _, col := range cols {
		totalDistance += int(math.Abs(float64(col - medianCol)))
	}

	return totalDistance
}

The Go implementation follows the same algorithmic structure as the Python version. Slices are used to store row and column positions dynamically.

One Go-specific detail is that the math.Abs function operates on float64, so integer values must be converted before taking the absolute value and then converted back to int.

Because the problem constraints are small, integer overflow is not a concern in Go.

Worked Examples

Example 1

Input:

grid = [
  [1,0,0,0,1],
  [0,0,0,0,0],
  [0,0,1,0,0]
]

Friends are located at:

  • (0,0)
  • (0,4)
  • (2,2)

Step 1: Collect rows

Scanning row by row:

Cell Friend? rows
(0,0) Yes [0]
(0,4) Yes [0, 0]
(2,2) Yes [0, 0, 2]

Final:

rows = [0, 0, 2]

Median row:

rows[3 // 2] = rows[1] = 0

Step 2: Collect columns

Scanning column by column:

Cell Friend? cols
(0,0) Yes [0]
(2,2) Yes [0, 2]
(0,4) Yes [0, 2, 4]

Final:

cols = [0, 2, 4]

Median column:

cols[3 // 2] = cols[1] = 2

Step 3: Compute distances

Meeting point:

(0, 2)

Distance calculations:

Friend Distance
(0,0) 2
(0,4) 2
(2,2) 2

Total:

2 + 2 + 2 = 6

Answer:

6

Example 2

Input:

grid = [[1,1]]

Friend positions:

  • (0,0)
  • (0,1)

Step 1: Collect rows

rows = [0, 0]

Median row:

0

Step 2: Collect columns

cols = [0, 1]

Median column:

1

Step 3: Compute distance

Meeting point:

(0,1)

Distances:

Friend Distance
(0,0) 1
(0,1) 0

Total:

1

Answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(mn) Each cell is scanned a constant number of times
Space O(k) Stores positions of all friends

Here, k represents the number of friends in the grid.

The algorithm performs two traversals of the grid, one for rows and one for columns. Each traversal visits every cell exactly once, giving linear complexity relative to the grid size.

The extra space comes from storing the row and column coordinates of every friend.

Test Cases

from typing import List

class Solution:
    def minTotalDistance(self, grid: List[List[int]]) -> int:
        rows = []
        cols = []

        m = len(grid)
        n = len(grid[0])

        for r in range(m):
            for c in range(n):
                if grid[r][c] == 1:
                    rows.append(r)

        for c in range(n):
            for r in range(m):
                if grid[r][c] == 1:
                    cols.append(c)

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

        total = 0

        for row in rows:
            total += abs(row - median_row)

        for col in cols:
            total += abs(col - median_col)

        return total

solution = Solution()

assert solution.minTotalDistance(
    [[1,0,0,0,1],
     [0,0,0,0,0],
     [0,0,1,0,0]]
) == 6  # provided example

assert solution.minTotalDistance([[1,1]]) == 1  # two adjacent homes

assert solution.minTotalDistance(
    [[1],
     [0],
     [1]]
) == 2  # vertical alignment

assert solution.minTotalDistance(
    [[1,0,1]]
) == 2  # horizontal alignment

assert solution.minTotalDistance(
    [[1,0,0],
     [0,0,0],
     [0,0,1]]
) == 4  # opposite corners

assert solution.minTotalDistance(
    [[1,1,1]]
) == 2  # odd number in one row

assert solution.minTotalDistance(
    [[1],
     [1],
     [1]]
) == 2  # odd number in one column

assert solution.minTotalDistance(
    [[1,1],
     [1,1]]
) == 4  # dense small grid

assert solution.minTotalDistance(
    [[0,1,0],
     [1,0,1],
     [0,1,0]]
) == 4  # symmetric cross pattern

assert solution.minTotalDistance(
    [[1,0,0,1],
     [0,0,0,0],
     [1,0,0,1]]
) == 8  # four corners

Test Summary

Test Why
Example 1 Validates standard multi-point scenario
Example 2 Smallest horizontal configuration
Single column friends Tests vertical-only movement
Single row friends Tests horizontal-only movement
Opposite corners Ensures correct Manhattan computation
Odd count in one row Validates median selection
Odd count in one column Confirms vertical median behavior
Dense 2x2 grid Tests multiple valid medians
Symmetric cross Ensures balanced distance handling
Four corners Tests distributed extreme positions

Edge Cases

One important edge case occurs when all friends lie on the same row. In this situation, the vertical distance component is always zero, and only the horizontal median matters. A buggy implementation might unnecessarily complicate the row handling or choose an incorrect meeting row. This solution handles the case naturally because the median row becomes the shared row index, producing zero vertical cost.

Another important case is when the number of friends is even. In one-dimensional median problems, there can be multiple optimal median positions. For example, with column positions [0, 1], both 0 and 1 produce the same minimal total distance. Some implementations incorrectly assume there is only one valid median. This solution correctly uses either middle element, which always yields an optimal answer.

A third edge case occurs when friends are spread across opposite corners of the grid. This maximizes distances and can expose mistakes in Manhattan distance calculations. For example:

[
  [1,0,0,1],
  [0,0,0,0],
  [1,0,0,1]
]

The implementation correctly separates row and column minimization, ensuring the optimal center region is selected without needing to explicitly test every candidate cell.