4.11 Best Meeting Point

4.11.1 Problem Metadata

4.11.2 Description

Given a 2D grid of 0s and 1s where each 1 represents a friend’s home, find the meeting point that minimizes the total Manhattan distance from all homes.

4.11.3 Examples

Input: [[1,0,0,0,1],
        [0,0,0,0,0],
        [0,0,1,0,0]]
Output: 6

4.11.4 Constraints

  • 1 <= rows, cols <= 200

4.11.5 Solution - Median Trick

4.11.5.1 Walkthrough

The Manhattan distance sum is minimized by the median of row coordinates and column coordinates separately. Collect all row indices, all column indices, take medians, then sum absolute differences to these medians.

4.11.5.2 Analysis

  • Time Complexity: O(m * n)
  • Space Complexity: O(m + n)

4.11.5.3 Implementation Steps

  1. Traverse the grid, collect row indices (rows) and column indices (cols) for all homes.
  2. Sort lc-lists (or rows inherently non-decreasing if traversed row-by-row).
  3. Median row = rows[rows.size/2], same for columns.
  4. Sum absolute differences from medians.

4.11.5.4 Code - Java

public int minTotalDistance(int[][] grid) {
    List<Integer> rows = new ArrayList<>();
    List<Integer> cols = new ArrayList<>();

    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == 1) {
                rows.add(r);
            }
        }
    }

    for (int c = 0; c < grid[0].length; c++) {
        for (int r = 0; r < grid.length; r++) {
            if (grid[r][c] == 1) {
                cols.add(c);
            }
        }
    }

    int rowMedian = rows.get(rows.size() / 2);
    int colMedian = cols.get(cols.size() / 2);

    int distance = 0;
    for (int r : rows) {
        distance += Math.abs(r - rowMedian);
    }
    for (int c : cols) {
        distance += Math.abs(c - colMedian);
    }

    return distance;
}