Problem Description

The "Best Meeting Point" problem asks you to find a location on a 2D grid where a group of people can meet so that the sum of their travel distances is minimized. The grid is represented as a 2D list of integers, where a cell with value 1 means a person is located there and 0 means the cell is empty.

Your task is to return the minimum total Manhattan distance (the sum of absolute differences of their coordinates) for all people to meet at a single grid cell. Any cell can be chosen as the meeting point, and multiple people can start from the same row or column.

• There is at least one person on the grid.
• All people must gather at one cell (the meeting point).
• The grid can be any size, but is typically not huge.
• There is only one valid answer for the minimum total distance.
• Do not move people to more than one meeting point.

Thought Process

At first glance, it might seem natural to try all possible meeting points and calculate the sum of distances for each. However, this brute-force approach would be very slow for larger grids, as it would require checking every cell for every person.

To optimize, we need to realize that the Manhattan distance is the sum of the absolute differences along each axis (row and column). This means we can separate the problem into two 1D problems: one for rows and one for columns. For each dimension, the optimal meeting point is at the median of the people's coordinates. This is because the median minimizes the sum of absolute differences.

So, the key insight is that we should:

• Collect all the row indices and column indices where people are located.
• Find the median of the row indices and the median of the column indices.
• Sum the distances from each person to these median coordinates.

Solution Approach

Let's break down the optimized solution step by step:

1. Collect the coordinates:
   • Iterate through the grid. For every cell with a 1, record its row and column indices.
   • Store all row indices in one list, and all column indices in another.
2. Sort the lists:
   • Sort the row and column lists. This is necessary to find the median efficiently.
3. Find the median:
   • The median is the middle value in the sorted list. If the list has an even number of elements, either of the two middle values works for minimizing the sum of distances.
4. Calculate the total distance:
   • For each person, compute the absolute difference between their row (and column) and the median row (and column).
   • Sum all these differences to get the minimum total distance.
5. Return the result:
   • The final answer is the sum of distances along both axes.

This approach is efficient because sorting and median-finding are much faster than checking every possible meeting point.

Example Walkthrough

Let's consider the following grid:

    1 0 0 0 1
    0 0 0 0 0
    0 0 1 0 0
  

Step-by-step:

1. Collect coordinates:
   • People are at (0,0), (0,4), and (2,2).
   • Row indices: [0, 0, 2]
   • Column indices: [0, 4, 2]
2. Sort lists:
   • Rows: [0, 0, 2]
   • Columns: [0, 2, 4]
3. Find medians:
   • Median row: 0 (middle of [0, 0, 2])
   • Median column: 2 (middle of [0, 2, 4])
4. Calculate distances:
   • For rows: |0-0| + |0-0| + |2-0| = 0 + 0 + 2 = 2
   • For columns: |0-2| + |4-2| + |2-2| = 2 + 2 + 0 = 4
5. Total distance:
   • 2 (rows) + 4 (columns) = 6

So, the minimum total distance is 6, with the best meeting point at (0,2).

Time and Space Complexity

• Brute-force approach:
  • For each cell, calculate the sum of distances to all people. If there are m rows, n columns, and k people, the complexity is O(m * n * k).
  • This is very slow for large grids.
• Optimized approach:
  • Collecting coordinates: O(m * n)
  • Sorting rows and columns: O(k log k), where k is the number of people.
  • Calculating distances: O(k)
  • Total time complexity: O(m * n + k log k)
  • Space complexity: O(k) for storing coordinates.

Summary

The Best Meeting Point problem leverages the property that the sum of Manhattan distances is minimized at the median. By separating the rows and columns and focusing on their medians, we avoid brute-force searching and achieve an efficient solution. This approach is elegant and powerful, transforming a complex 2D problem into two simple 1D problems.

Code Implementation

class Solution:
    def minTotalDistance(self, grid):
        rows = []
        cols = []
        m, n = len(grid), len(grid[0])
        # Collect row indices
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    rows.append(i)
        # Collect column indices
        for j in range(n):
            for i in range(m):
                if grid[i][j] == 1:
                    cols.append(j)
        # Find median
        def minDist(points):
            points.sort()
            median = points[len(points)//2]
            return sum(abs(p - median) for p in points)
        return minDist(rows) + minDist(cols)
      

class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
        vector<int> rows, cols;
        int m = grid.size(), n = grid[0].size();
        // Collect row indices
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == 1) rows.push_back(i);
        // Collect column indices
        for (int j = 0; j < n; ++j)
            for (int i = 0; i < m; ++i)
                if (grid[i][j] == 1) cols.push_back(j);
        // Find median and sum distances
        auto minDist = [](vector<int>& points) {
            sort(points.begin(), points.end());
            int median = points[points.size() / 2];
            int total = 0;
            for (int p : points)
                total += abs(p - median);
            return total;
        };
        return minDist(rows) + minDist(cols);
    }
};
      

class Solution {
    public int minTotalDistance(int[][] grid) {
        List<Integer> rows = new ArrayList<>();
        List<Integer> cols = new ArrayList<>();
        int m = grid.length, n = grid[0].length;
        // Collect row indices
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == 1) rows.add(i);
        // Collect column indices
        for (int j = 0; j < n; ++j)
            for (int i = 0; i < m; ++i)
                if (grid[i][j] == 1) cols.add(j);
        // Find median and sum distances
        int total = minDist(rows) + minDist(cols);
        return total;
    }
    private int minDist(List<Integer> points) {
        Collections.sort(points);
        int median = points.get(points.size() / 2);
        int sum = 0;
        for (int p : points)
            sum += Math.abs(p - median);
        return sum;
    }
}
      

var minTotalDistance = function(grid) {
    let rows = [], cols = [];
    let m = grid.length, n = grid[0].length;
    // Collect row indices
    for (let i = 0; i < m; ++i)
        for (let j = 0; j < n; ++j)
            if (grid[i][j] === 1) rows.push(i);
    // Collect column indices
    for (let j = 0; j < n; ++j)
        for (let i = 0; i < m; ++i)
            if (grid[i][j] === 1) cols.push(j);
    // Find median and sum distances
    function minDist(points) {
        points.sort((a, b) => a - b);
        let median = points[Math.floor(points.length / 2)];
        return points.reduce((sum, p) => sum + Math.abs(p - median), 0);
    }
    return minDist(rows) + minDist(cols);
};