Best Meeting Point

XXX. Minimum Total Distance

Matrix

Sorting

Median

Problem Statement:

Given a 2D grid where some cells contain people (1) and others are empty (0), find the minimum total distance to move everyone to a meeting point. The meeting point should minimize the Manhattan distance between all people and the meeting point.

Algorithm:

1. Collect all the row and column indices of cells containing 1.
   • Rows are collected in the order of traversal (already sorted).
   • Columns are collected and then sorted to find the median efficiently.
2. Find the median of the rows and columns:
   • The median minimizes the total Manhattan distance for 1D points.
3. Calculate the total Manhattan distance by summing up distances from each row and column to their respective medians.

Complexity:

Time Complexity: O(m × n + n log n), where m and n are the number of rows and columns in the grid.
Space Complexity: O(k), where k is the number of people in the grid.

Java Implementation:

public int minTotalDistance(int[][] grid) {
    // List to store the row and column indices of all people
    List rows = new ArrayList<>();
    List cols = new ArrayList<>();
    int distance = 0;

    // Collect row and column indices
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == 1) {
                rows.add(i); // Rows are already sorted due to traversal order
                cols.add(j);
            }
        }
    }

    // Sort columns to find the median
    Collections.sort(cols);

    // Find the median row and column
    int row = rows.get(rows.size() / 2);
    int col = cols.get(cols.size() / 2);

    // Calculate the minimum distance in 1D for rows and columns
    distance += minDist1d(rows, row);
    distance += minDist1d(cols, col);

    return distance;
}

// Helper function to calculate 1D Manhattan distance
public int minDist1d(List points, int origin) {
    int distance = 0;
    for (int point : points)
        distance += Math.abs(point - origin);
    return distance;
}
                

Python Implementation:

def minTotalDistance(grid):
    # Helper function to calculate 1D Manhattan distance
    def minDist1d(points, origin):
        return sum(abs(point - origin) for point in points)

    rows = []
    cols = []
    
    # Collect row and column indices
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                rows.append(i)
                cols.append(j)

    # Sort columns to find the median
    cols.sort()
    row = rows[len(rows) // 2]
    col = cols[len(cols) // 2]

    # Calculate the minimum distance
    return minDist1d(rows, row) + minDist1d(cols, col)
                

C++ Implementation:

int minTotalDistance(vector>& grid) {
    vector rows, cols;

    // Collect row and column indices
    for (int i = 0; i < grid.size(); i++)
        for (int j = 0; j < grid[0].size(); j++)
            if (grid[i][j] == 1) {
                rows.push_back(i);
                cols.push_back(j);
            }

    // Sort columns to find the median
    sort(cols.begin(), cols.end());
    int row = rows[rows.size() / 2];
    int col = cols[cols.size() / 2];

    // Helper lambda for 1D Manhattan distance
    auto minDist1d = [](vector& points, int origin) {
        int distance = 0;
        for (int point : points)
            distance += abs(point - origin);
        return distance;
    };

    // Calculate total distance
    return minDist1d(rows, row) + minDist1d(cols, col);
}