Shortest Distance from All Buildings

HardGraphsbfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a grid where 0 is empty land you can walk through, 1 is a building, and 2 is an obstacle. You want to build a house on one empty cell so that the sum of its walking distances to **every** building is as small as possible. Walking moves one step up, down, left or right. You may only step onto empty land, except that the final step into a building is allowed (you cannot walk through a building). The distance to a building is the fewest steps from the house cell into that building. Return the minimum total distance. If no empty cell can reach all buildings, return -1. The grid contains at least one building.

Examples

Input: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7
A house at (1,2) is 3 steps from each top building and 1 step from the bottom one, for a total of 7.
Input: grid = [[1,0]]
Output: 1
The only empty cell is next to the building.
Input: grid = [[1]]
Output: -1
There is no empty land to build on.

Constraints

  • 1 <= rows, cols <= 50
  • `grid[i][j]` is 0, 1 or 2
  • There is at least one building.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bfs problems