We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Best Meeting Point

Number: 296

Difficulty: Hard

Paid? Yes

Companies: Meta, Google, DoorDash, Amazon, X

Problem Description

Given an m x n binary grid where each 1 marks the home of one friend, the goal is to find a meeting point (an empty cell) that minimizes the total travel distance from all the friends’ houses. The travel distance is defined by Manhattan Distance: the sum of absolute differences of the x and y coordinates.

Key Insights

  • The optimal meeting point in one dimension is the median of the coordinates, which minimizes the sum of absolute deviations.
  • We can handle the two dimensions (rows and columns) independently by collecting the row and column indices of each friend.
  • Sorting the coordinates or traversing in a smart order (for instance, rows are naturally sorted when scanning row-wise) allows easy extraction of the median.
  • The total minimum distance is the sum of the absolute differences between each friend’s row/column index and the median row/column index.

Space and Time Complexity

Time Complexity: O(m*n) to traverse the grid and O(F) to compute the distance, where F is the number of friends (1s in grid).
Space Complexity: O(F) for storing the row and column indices of the friends.

Solution

The solution first collects all the row indices and column indices of the friend locations. For the row indices, a simple row-wise traversal suffices as they will be naturally sorted. For the column indices, iterate column-by-column to get sorted order. Next, the median position is computed for both rows and columns. This median minimizes the sum of distances on that axis. Finally, compute the total Manhattan distance from each friend’s location to the median point by summing up the absolute differences between their indices and the medians. The key trick is understanding that Manhattan distance minimization can be split into two 1D problems, each solved by the median.

Code Solutions

# Function to compute the minimal total travel distance for all friends' houses
def minTotalDistance(grid):
    rows = []  # List to store row indices of all homes
    cols = []  # List to store column indices of all homes

    # Collect row indices; row-wise traversal gives naturally sorted row indices
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                rows.append(i)

    # Collect column indices; traverse column-wise to get sorted order
    for j in range(len(grid[0])):
        for i in range(len(grid)):
            if grid[i][j] == 1:
                cols.append(j)

    # Find the median row and column
    mid_row = rows[len(rows) // 2]
    mid_col = cols[len(cols) // 2]

    # Calculate total Manhattan distance to the median point (mid_row, mid_col)
    total_distance = 0
    for r in rows:
        total_distance += abs(r - mid_row)
    for c in cols:
        total_distance += abs(c - mid_col)

    return total_distance

# Example usage:
grid = [
    [1,0,0,0,1],
    [0,0,0,0,0],
    [0,0,1,0,0]
]
print(minTotalDistance(grid))  # Expected output: 6
← Back to All Questions