Coding

Shortest Distance from All Buildings

Asked at

Amazon

Meta

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

You are given an m x n grid grid of values 0, 1, or 2, where:

each 0 marks an empty land that you can pass by freely,
each 1 marks a building that you cannot pass through, and
each 2 marks an obstacle that you cannot pass through. You want to build a house on an empty land that reaches all buildings in the shortest total travel distance. You can only move up, down, left, and right. Return the shortest travel distance for such a house. If it is not possible to build such a house according to the above rules, return -1. 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: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]] Output: 7 Explanation: Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2). The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal. So return 7.

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

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

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] is either 0, 1, or 2.
There will be at least one building in the grid.

cpp

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        // User code goes here
    }
};

java

class Solution {
    public int shortestDistance(int[][] grid) {
        // User code goes here
    }
}

python

class Solution:
    def shortestDistance(self, grid):
        # User code goes here

javascript

class Solution {
    shortestDistance(grid) {
        // User code goes here
    }
}

csharp

public class Solution
{
    public int ShortestDistance(int[][] grid)
    {
        // User code goes here

    }
}

func shortestDistance(grid [][]int) int {
    //your code goes here
}

Stuck? Show a way to structure it+

01For each building, run BFS through empty land.
02Accumulate distance and reach count per empty cell.
03Never traverse obstacles or other buildings.
04After all BFS runs, consider cells reached by every building.
05Return their minimum distance or minus one.

Reference answer

Run a separate BFS from each building because all edges have equal cost. Maintain two matrices: totalDistance and reachedCount. During a building's BFS, traverse only empty cells, keeping a level distance; when an empty cell is visited, add that distance and increment its count. Do not walk through obstacles or other buildings. After processing every building, an empty cell is a valid house location only if its count equals the number of buildings; choose the smallest totalDistance among those cells. This correctly rejects an empty region unreachable from even one building. With B buildings and an m by n grid, time is O(B times m times n), and the matrices plus queue use O(m times n) space. A useful optimization is to restrict later BFS traversals to cells reached by all earlier buildings, but first articulate the simpler correct version.

Then expect these follow-ups

How can reach-count pruning reduce later BFS work?
Tests: follow-up reasoning
What changes if each building has a weight?
Tests: constraint adaptation

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question