296. Best Meeting Point - Detailed Explanation

Problem Statement

You are given an m x n grid, where:

• A cell with value 1 indicates the presence of a person.
• A cell with value 0 indicates an empty space.

Your task is to find the meeting point that minimizes the total Manhattan distance between that point and all the 1’s in the grid. The Manhattan distance between two points (x1, y1) and (x2, y2) is calculated as:

  distance = |x1 - x2| + |y1 - y2|

Return the minimum total Manhattan distance. If there is no person (1) in the grid, the answer would be 0.

Example:

• Input:

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

• Output: 6
• Explanation:
  The positions of the persons are: (0,0), (0,4), and (2,2).
  The optimal meeting point is (0,2).
  Total distance = |0-0| + |0-2| (from (0,0))
  + |0-0| + |4-2| (from (0,4))
  + |2-0| + |2-2| (from (2,2))
  = 2 + 2 + 2 = 6

Hints

• Hint 1:
  Notice that the Manhattan distance is separable into its x-coordinate (row) and y-coordinate (column) components. This means you can independently determine the best meeting row and best meeting column.

• Hint 2:
  For a set of points along one dimension, the median minimizes the sum of absolute differences. Thus, the best meeting row is the median of all row indices of homes, and the best meeting column is the median of all column indices of homes.

• Hint 3:
  You can obtain the list of rows by iterating over the grid row-by-row. The list of row indices will naturally be sorted. For columns, iterate column-by-column or collect the column indices and sort them.

Approach: Use Medians on Rows and Columns

Step 1: Collect Coordinates

• Row Coordinates:
  Traverse the grid row by row. For every cell with a value of 1, add its row index to a list.

• Column Coordinates:
  Traverse the grid column by column (or during the same pass, collect the column index for every 1). This list might not be sorted naturally, so sort it afterward if needed.

Step 2: Find the Medians

• The median of the row indices gives the optimal meeting row.
• The median of the column indices gives the optimal meeting column.

Step 3: Calculate Total Manhattan Distance

• For each home (cell with 1), compute the distance from that home to the meeting point:
  • Distance = |home_row − median_row| + |home_col − median_col|
• Sum all these distances. This sum is the minimum total Manhattan distance.

Why Medians Work

The median minimizes the sum of absolute deviations. For example, if you have points on a number line, choosing the median minimizes the total travel distance. Since Manhattan distance is simply the sum of absolute differences in each coordinate, the optimal meeting point is (median_row, median_col).

Code Implementation

Python Code