# Shortest Distance from All Buildings

This page explains Java solution to problem `Shortest Distance from All Buildings` using `Breadth First Search` algorithm.

## Problem Statement

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move `up`, `down`, `left` and `right`. You are given a `2D` grid of values `0`, `1` or `2`, where:

Example 1:

Input:
[
[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.

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class ShortestDistanceFromAllBuildings {
public int shortestDistance(int[][] grid) {
if(grid == null || grid.length == 0) return 0;

int m = grid.length;
int n = grid.length;

int[][] total = new int[m][n];
int[][] count = new int[m][n];

int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int totalBuilding = 0;

for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == 1) {
totalBuilding++;
boolean[][] visited = new boolean[m][n];

q.offer(new int[]{i, j});
int level = 0;
while(!q.isEmpty()) {
int size = q.size();
for(int e = 0; e < size; e++) {
int[] point = q.poll();

int x = point;
int y = point;

if(visited[x][y] || grid[x][y] == 2) continue;

visited[x][y] = true;
for(int[] dir: dirs) {
int xNew = x + dir;
int yNew = y + dir;

if(xNew >= 0 && xNew < grid.length && yNew >= 0 && yNew < grid.length
&& grid[xNew][yNew] != 1 && grid[xNew][yNew] != 2) {
q.offer(new int[]{xNew, yNew});
}
}

if(grid[x][y] == 0) {
total[x][y] += level;
count[x][y]++;
}
}
level++;
}
}
}
}

int res = Integer.MAX_VALUE;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(count[i][j] == totalBuilding) res = Math.min(res, total[i][j]);
}
}
return res == Integer.MAX_VALUE ? -1 : res;
}
}
``````

## Time Complexity

O((M * N)2)
M is total number of rows in an input array
N is total number of cols in an input array

## Space Complexity

O(M * N) Where
M is total number of rows in an input array
N is total number of cols in an input array