296. Best Meeting Point
Problem Description
In this problem, you are given a m x n
binary grid, where each cell in the grid can either contain a 1
(which represents the home of a friend) or a 0
(which signifies an empty space). The goal is to find the minimal total travel distance to a single meeting point.
The "total travel distance" is defined as the sum of all distances from the homes of each friend (cells with a 1
) to the meeting point. When calculating distances, we use the Manhattan Distance, which means the distance between two points is the sum of the absolute differences of their coordinates. For two points p1
and p2
, the Manhattan Distance is |p2.x - p1.x| + |p2.y - p1.y|
.
The challenge of the problem lies in finding the optimal meeting point that minimizes the total travel distance for all friends.
Intuition
The intuition behind the solution is based on properties of the Manhattan Distance in a grid. When considering the distance along one axis (either horizontal or vertical), the best meeting point minimizes the distance to all points along that axis. In a one-dimensional space, this is the median of all points because it ensures that the sum of distances to the left and right (or up and down) are minimized.
The solution consists of two steps:
-
Separately find the best meeting point for rows and columns. By treating the rows and columns independently and finding the medians, we effectively split the problem into two one-dimensional issues.
-
Calculate the sum of Manhattan Distances from all friends' homes to the found meeting point.
To find the medians:
-
First, we iterate through the grid and store the row and column numbers of all cells with a '1' into separate lists -
rows
andcols
. -
The median for the rows is simply the middle element of the
rows
list. This works because the grid rows are already indexed in sorted order. -
For the columns, since we collect them in the order they appear while iterating over the rows, we need to sort the
cols
list before finding the middle element, which serves as the median.
Finally, the function f(arr, x)
calculates the sum of distances of all points in arr
to point x
, the median. The minTotalDistance
function returns the sum of f(rows, i)
and f(cols, j)
, where i
and j
are the median row and column indices, representing the optimal meeting point.
Solution Approach
The implementation of the solution starts by defining a helper function f(arr, x)
which is responsible for calculating the total Manhattan Distance for a list of coordinates, arr
, to a given point x
. Using the Manhattan Distance formula, we sum up abs(v - x)
for all values v
in arr
, representing either all the x-coordinates or y-coordinates of friends' homes.
In the main function minTotalDistance
, we first create two lists, rows
and cols
. These lists will store the x and y coordinates, respectively, of all friends' homes. We achieve this by iterating through every cell in the grid with nested loops. When we find a cell with a 1
, we append the row index i
to rows
and the column index j
to cols
.
The next step is to sort cols
. The rows
are already in sorted order because weāve collected them by iterating through each row in sequence. However, cols
are collected out of order, so we must sort them to determine the median accurately.
Once we have our sorted lists, we find the medians by selecting the middle elements of the rows
and cols
lists. These are our optimal meeting points along each axis. Here, the bitwise right shift operator >>
is used to find the index of the median quickly. It's equivalent to dividing the length of the list by 2. We calculate i = rows[len(rows) >> 1]
for rows and j = cols[len(cols) >> 1]
for columns.
Finally, we sum up the total Manhattan Distance from all friends' homes to the median points by calling f(rows, i) + f(cols, j)
. This sum represents the minimal total travel distance that all friends have to travel to meet at the optimal meeting point, and it is returned as the solution to the problem.
This implementation utilizes basic algorithm concepts, such as iteration, sorting, and median selection coupled with mathematical insight specific to the problem contextāthe Manhattan Distance formula. The approach is efficient as it breaks down a seemingly complex two-dimensional problem into two easier one-dimensional problems by exploiting properties of the Manhattan Distance in a grid.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small 3x3 binary grid example:
Grid: 1 0 0 0 1 0 0 0 1
The grid shows that we have three friends living in different homes, each marked by 1
. They are trying to find the best meeting point.
Following the approach:
-
We first iterate over the grid row by row, and whenever we find a
1
, we store the row and column indices in separate lists:rows = [0, 1, 2]
(Already in sorted order, since we are going row by row).cols = [0, 1, 2]
(These happen to be in sorted order, but in general, this wouldn't be the case, and we would need to sort this list).
-
Since both
rows
andcols
lists are already sorted, we find the medians directly. Length of both lists is3
:- Median row index
i = rows[3 >> 1] = rows[1] = 1
. - Median column index
j = cols[3 >> 1] = cols[1] = 1
.
- Median row index
We have determined that the best meeting point is at the cell with coordinates (1,1), which is also the home of one of the friends, in the center of the grid.
-
Next, we calculate the Manhattan Distance for each friend to the meeting point using the helper function
f(arr, x)
:f(rows, i) = abs(0 - 1) + abs(1 - 1) + abs(2 - 1) = 1 + 0 + 1 = 2
.f(cols, j) = abs(0 - 1) + abs(1 - 1) + abs(2 - 1) = 1 + 0 + 1 = 2
.
-
The minimal total travel distance is the sum of the distances calculated, which is
2 + 2 = 4
.
This total distance of 4
represents the minimum travel distance for all friends to meet at the (1,1) cell in the grid. This conclusion is reached following the properties of Manhattan Distance and the strategy of using medians to minimize the travel distance.
Solution Implementation
1class Solution:
2 # Method to calculate the minimum total distance
3 def minTotalDistance(self, grid: List[List[int]]) -> int:
4 # Helper function to calculate the distance to the median element 'median' from all elements in 'elements'
5 def calculate_distance(elements, median):
6 return sum(abs(element - median) for element in elements)
7
8 # List to record the positions of '1's in rows and columns
9 row_positions, col_positions = [], []
10
11 # Loop through the grid to find positions of '1's
12 for row_index, row in enumerate(grid):
13 for col_index, cell in enumerate(row):
14 if cell: # If the cell is '1', record its position
15 row_positions.append(row_index)
16 col_positions.append(col_index)
17
18 # Sort the column positions to easily find the median
19 col_positions.sort()
20
21 # Find medians of rows and columns positions for '1'',s
22 # since the list is sorted/constructed in order, the median is the middle value
23 row_median = row_positions[len(row_positions) // 2]
24 col_median = col_positions[len(col_positions) // 2]
25
26 # Calculate the total distance using the median of rows and columns
27 total_distance = calculate_distance(row_positions, row_median) + calculate_distance(col_positions, col_median)
28
29 return total_distance
30
1class Solution {
2 public int minTotalDistance(int[][] grid) {
3 // The grid dimensions
4 int rows = grid.length;
5 int cols = grid[0].length;
6
7 // Lists to store the coordinates of all 1s in the grid
8 List<Integer> iCoordinates = new ArrayList<>();
9 List<Integer> jCoordinates = new ArrayList<>();
10
11 // Iterate through the grid to populate the lists with the coordinates of 1s
12 for (int i = 0; i < rows; ++i) {
13 for (int j = 0; j < cols; ++j) {
14 if (grid[i][j] == 1) {
15 iCoordinates.add(i);
16 jCoordinates.add(j);
17 }
18 }
19 }
20
21 // Sort the columns' coordinates as row coordinates are already in order because of the way they are added
22 Collections.sort(jCoordinates);
23
24 // Find the median of the coordinates, which will be our meeting point
25 int medianRow = iCoordinates.get(iCoordinates.size() >> 1);
26 int medianCol = jCoordinates.get(jCoordinates.size() >> 1);
27
28 // Calculate the total distance to the median points
29 int totalDistance = calculateDistance(iCoordinates, medianRow) + calculateDistance(jCoordinates, medianCol);
30 return totalDistance;
31 }
32
33 // Helper function to calculate the total distance all 1s to the median along one dimension
34 private int calculateDistance(List<Integer> coordinates, int median) {
35 int sum = 0;
36 for (int coordinate : coordinates) {
37 sum += Math.abs(coordinate - median);
38 }
39 return sum;
40 }
41}
42
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 int minTotalDistance(std::vector<std::vector<int>>& grid) {
7 int numRows = grid.size(); // Row count of the grid
8 int numCols = grid[0].size(); // Column count of the grid
9 std::vector<int> rowPositions; // Stores the row positions of 1s in the grid
10 std::vector<int> colPositions; // Stores the column positions of 1s in the grid
11
12 // Collect positions of 1s (people) in each dimension
13 for (int row = 0; row < numRows; ++row) {
14 for (int col = 0; col < numCols; ++col) {
15 if (grid[row][col]) {
16 rowPositions.emplace_back(row);
17 colPositions.emplace_back(col);
18 }
19 }
20 }
21
22 // Sort the positions of the columns as they may not be in order
23 sort(colPositions.begin(), colPositions.end());
24
25 // Find the median position for persons in grid for rows and columns separately
26 int medianRow = rowPositions[rowPositions.size() / 2];
27 int medianCol = colPositions[colPositions.size() / 2];
28
29 // Lambda function to calculate the total distance for 1 dimension
30 auto calculateDistance = [](const std::vector<int>& positions, int median) {
31 int sumDistances = 0;
32 for (int position : positions) {
33 sumDistances += std::abs(position - median);
34 }
35 return sumDistances;
36 };
37
38 // Calculate total distance to the median row and median column
39 return calculateDistance(rowPositions, medianRow) + calculateDistance(colPositions, medianCol);
40 }
41};
42
1function minTotalDistance(grid: number[][]): number {
2 const numRows = grid.length; // Row count of the grid
3 const numCols = grid[0].length; // Column count of the grid
4 const rowPositions: number[] = []; // Stores the row positions of 1s in the grid
5 const colPositions: number[] = []; // Stores the column positions of 1s in the grid
6
7 // Collect positions of 1s (people) in each dimension
8 for (let row = 0; row < numRows; ++row) {
9 for (let col = 0; col < numCols; ++col) {
10 if (grid[row][col] === 1) {
11 rowPositions.push(row);
12 colPositions.push(col);
13 }
14 }
15 }
16
17 // Sort the positions of the columns as they may not be in order
18 colPositions.sort((a, b) => a - b);
19
20 // Find the median position for people in grid for rows and columns separately
21 const medianRow = rowPositions[Math.floor(rowPositions.length / 2)];
22 const medianCol = colPositions[Math.floor(colPositions.length / 2)];
23
24 // Function to calculate the total distance for one dimension
25 const calculateDistance = (positions: number[], median: number): number => {
26 return positions.reduce((sumDistances, position) => {
27 return sumDistances + Math.abs(position - median);
28 }, 0);
29 };
30
31 // Calculate total distance to the median row and median column
32 return calculateDistance(rowPositions, medianRow) + calculateDistance(colPositions, medianCol);
33}
34
Time and Space Complexity
The time complexity of the given code is primarily determined by two factors: the traversal of the grid once and the sorting of the column indices.
-
Traversing the Grid: Since every cell of the grid is visited once, this operation has a time complexity of
O(mn)
wherem
is the number of rows andn
is the number of columns in the grid. -
Sorting the Columns: The sorting operation is applied to the list containing the column indices, where the worst case is when all the cells have a 1, and hence the list contains
mn
elements. Sorting a list ofn
elements has a time complexity ofO(n log n)
. Thus, the complexity for sorting the column array isO(mn log(mn))
.
With these operations, the total time complexity is the sum of individual complexities. However, since O(mn log(mn))
dominates O(mn)
, the overall time complexity is O(mn log(mn))
.
For space complexity:
- Storing the Rows and Columns:
In the worst case, we store the row index for
mn
ones and the same for the column index. Thus, the space complexity isO(2mn)
which simplifies toO(mn)
because constant factors are neglected in Big O notation.
Therefore, the final time complexity is O(mn log(mn))
and the space complexity is O(mn)
.
Learn more about how to find time and space complexity quickly using problem constraints.
A heap is a ...?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!