Practice/Google/Leetcode 296. Best Meeting Point

Leetcode 296. Best Meeting Point

CodingMust

Problem

You are given a 2D grid where each cell is either empty (represented by 0) or contains a home (represented by 1). Your task is to find the minimum total Manhattan distance from all homes to a single meeting point in the grid.

The Manhattan distance between two points (r1, c1) and (r2, c2) is calculated as: |r1 - r2| + |c1 - c2|

The meeting point can be any cell in the grid (including cells with homes or empty cells). Return the minimum total Manhattan distance achievable.

Requirements

1. Calculate the minimum sum of Manhattan distances from all homes to a single meeting point
2. The meeting point can be located at any cell in the grid
3. Return the minimum total distance as an integer

Constraints

• 1 ≤ grid.length, grid[0].length ≤ 200
• grid[i][j] is either 0 or 1
• There will be at least one home in the grid
• Time complexity should be O(m × n) where m and n are the grid dimensions
• Space complexity should be O(m + n) or better

Examples

Example 1:

Input: grid = [ [1,0,0,0,1], [0,0,0,0,0], [0,0,1,0,0] ] Output: 6 Explanation: The homes are at positions (0,0), (0,4), and (2,2). The optimal meeting point is (0,2). The total distance is: |0-0| + |2-0| + |0-0| + |2-4| + |2-2| + |2-2| = 0+2+0+2+2+0 = 6

Example 2:

Input: grid = [[1,0,1],[0,0,0],[1,0,1]] Output: 8 Explanation: Four homes at the corners. Meeting at the center (1,1) gives: 4 homes × 2 distance each = 8 total

Example 3:

Input: grid = [[1]] Output: 0 Explanation: Only one home, so the meeting point is at the home itself