Best Meeting Point - Practice Coding Problems

Best Meeting Point - Problem

Given an m x n binary grid grid where each 1 marks the home of one friend, return the minimal total travel distance.

The total travel distance is the sum of the distances between the houses of the friends and the meeting point.

The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Input & Output

Example 1 — Basic 3x5 Grid

$ Input: grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]

› Output: 6

💡 Note: Friends are at (0,0), (0,4), and (2,2). The optimal meeting point is (0,2) with total distance = |0-0|+|0-2| + |0-0|+|4-2| + |2-0|+|2-2| = 2+2+2 = 6

Example 2 — Single Row

$ Input: grid = [[1,1]]

› Output: 1

💡 Note: Two friends at (0,0) and (0,1). Meeting at either location gives distance 1. Optimal is anywhere between them.

Example 3 — Single Friend

$ Input: grid = [[1]]

› Output: 0

💡 Note: Only one friend, so meeting point is at their location with distance 0

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 200
grid[i][j] is either 0 or 1
There will be at least one friend in the grid

Visualization

Tap to expand

Understanding the Visualization

Input

Binary grid with 1s marking friend locations

Process

Find optimal meeting point using median coordinates

Output

Return minimum total travel distance

Key Takeaway

🎯 Key Insight: The optimal meeting point is at the intersection of median row and median column coordinates

Asked in

G Google 15 f Facebook 12 Apple 8 a Amazon 6

The key insight is that Manhattan distance separates into independent x and y components. The median of each dimension minimizes the sum of absolute deviations. Best approach uses mathematical optimization with median coordinates. Time: O(k log k), Space: O(k) where k is number of friends.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try Every Point	O(m²n²)	O(k)	Try every possible meeting point and calculate total Manhattan distance
Mathematical Optimization	O(k log k)	O(k)	Use median property to find optimal meeting point mathematically

Brute Force - Try Every Point — Algorithm Steps

Extract all friend positions from the grid
For each possible meeting point (i,j)
Calculate sum of Manhattan distances to all friends
Keep track of minimum total distance

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Friends

Find all positions with value 1

Test All Points

For each cell, sum Manhattan distances to all friends

Find Minimum

Return the smallest total distance found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int** grid, int gridSize, int* gridColSize) {
    if (gridSize == 0 || gridColSize[0] == 0) return 0;
    
    int m = gridSize, n = gridColSize[0];
    int friends[100][2]; // Assume max 100 friends
    int friendCount = 0;
    
    // Extract friend positions
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                friends[friendCount][0] = i;
                friends[friendCount][1] = j;
                friendCount++;
            }
        }
    }
    
    if (friendCount == 0) return 0;
    
    int minDistance = INT_MAX;
    
    // Try every possible meeting point
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int totalDistance = 0;
            for (int k = 0; k < friendCount; k++) {
                totalDistance += abs(i - friends[k][0]) + abs(j - friends[k][1]);
            }
            if (totalDistance < minDistance) {
                minDistance = totalDistance;
            }
        }
    }
    
    return minDistance;
}

int main() {
    // Simple parsing for small test cases
    int grid[10][10] = {{1,0,0,0,1},{0,0,0,0,0},{0,0,1,0,0}};
    int* gridPtr[3] = {grid[0], grid[1], grid[2]};
    int colSizes[3] = {5, 5, 5};
    
    int result = solution(gridPtr, 3, colSizes);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m²n²)

Nested loops through all m×n cells, each calculating distance to all friends

⚠ Quadratic Growth

Space Complexity

O(k)

Only store friend positions where k is number of friends

✓ Linear Space

28.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try Every Point — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler