How should I practice Shortest Distance from All Buildings?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Waymo phone screen problems in FastPrep.

Is Shortest Distance from All Buildings associated with Waymo?

FastPrep tags this as a Waymo phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Shortest Distance from All Buildings

Learn this problem

● Hard

WaymoFULLTIMEPHONE SCREEN

Problem statement

You are given a rectangular grid where 0 is empty land, 1 is a building, and 2 is an obstacle.

Choose one empty cell on which to build a meeting point. Movement is allowed one cell up, down, left, or right through empty land. Buildings and obstacles cannot be crossed.

Return the minimum possible sum of shortest-path distances from the chosen empty cell to every building. Return -1 when no empty cell can reach every building.

Function

shortestDistance(grid: int[][]) → int

Examples

Example 1

grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]return = 7

Choosing row 1, column 2 gives distances 3, 3, and 1 to the three buildings, for total 7.

Example 2

grid = [[1,0]]return = 1

The only empty cell is one step from the building.

Example 3

grid = [[1]]return = -1

There is no empty cell on which to build the meeting point.

Constraints

1 <= grid.length, grid[0].length <= 50.
Every cell is 0, 1, or 2.
The grid contains at least one building.