Katkat
Back

Find the Best Meeting Point on a Grid

WaymoSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to use multi-source Breadth-First Search (BFS) to find a point that minimizes total travel distance across a grid with obstacles.

Problem Statement

You are given a 2D grid of size m x n representing a city, where each cell is either empty (0), contains a building (1), or contains an obstacle (2). You need to find an empty cell (0) that minimizes the sum of shortest-path distances to all buildings in the city.

Movement is allowed horizontally and vertically between adjacent empty cells. You cannot pass through buildings or obstacles. If there is no empty cell from which all buildings are reachable, return -1.

Function Signature

def findBestMeetingPoint(grid: List[List[int]]) -> int:

Input/Output

  • grid: A 2D list of integers where 0=empty, 1=building, 2=obstacle.
  • Return the minimum total distance. If no such cell exists, return -1.

Examples

Example 1:

Input: grid = [[1, 0, 0], [0, 0, 0], [0, 0, 1]]
Output: 4
Explanation: The cell (1, 1) is equidistant (distance 2) from both buildings, total = 4.

Example 2:

Input: grid = [[1, 0, 2], [2, 2, 2], [0, 0, 1]]
Output: -1
Explanation: There is no path between the two buildings due to the wall of obstacles.

Constraints

  • m, n are between 1 and 50.
  • Buildings are at least one.
  • You must account for reachability; if a building cannot reach a candidate cell, that cell is invalid.

Hints

Hint 1

Run a Breadth-First Search (BFS) starting from each building to calculate the distance to every reachable cell in the grid.

Hint 2

Maintain a global distance map (or 2D array) that accumulates the distances from all buildings and a counter map to keep track of how many buildings can reach a specific cell.

Hint 3

After processing all buildings, iterate through the grid to find an empty cell where the reachability count equals the total number of buildings, and pick the one with the minimum accumulated distance.

Follow-up questions

  • How would your approach change if the grid size increased to 1000x1000?
  • If the grid had 'teleporters' that connected two specific cells, how would you modify the graph traversal?
  • What is the time and space complexity of your solution in terms of buildings (B) and grid cells (N x M)?