317. Shortest Distance from All Buildings

/*
BFS for each building. Use reach 2D array to skip non reachable cells.
This solution does not modify the input grid.

Time Complexity:
= M*N + 1s * 0s
= M*N + K*(M*N - K)   (if K = number of buildings (1s))
= M*N + K*M*N - K^2
= O(K*M*N)

In worst case K = (M*N)/4...
For example.. there are M/2 rows that have buildings.. and each row has N/2 buildings
B E B E B E
E E E E E E
B E B E B E
E E E E E E
B E B E B E
E E E E E E
Thus worst case Time Complexity will be O((M^2) * (N^2))

Space Complexity: O(M * N)
M = Number of rows
N = Number of columns
K = Number of Buildings (1s)
*/
class Solution {
    private static final int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int shortestDistance(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return -1;
        }

        int rows = grid.length;
        int cols = grid[0].length;

        int[][] reach = new int[rows][cols];
        int[][] dist = new int[rows][cols];
        int minDist = Integer.MAX_VALUE;
        int bldg = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1) {
                    minDist = bfsHelper(grid, reach, dist, i, j, bldg);
                    if (minDist == Integer.MAX_VALUE) {
                        return -1;
                    }
                    bldg++;
                }
            }
        }

        return minDist == Integer.MAX_VALUE ? -1 : minDist;
    }

    private int bfsHelper(int[][] grid, int[][] reach, int[][] dist, int row, int col, int bldg) {
        int minDist = Integer.MAX_VALUE;
        int level = 1;

        Queue<int[]> queue = new LinkedList();
        queue.offer(new int[]{row, col});

        while (!queue.isEmpty()) {
            int qSize = queue.size();
            for (int q = 0; q < qSize; q++) {
                int[] cell = queue.poll();

                for (int[] dir : dirs) {
                    int x = cell[0] + dir[0];
                    int y = cell[1] + dir[1];

                    if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] != 0 || reach[x][y] != bldg) {
                        continue;
                    }

                    reach[x][y] = bldg+1;
                    dist[x][y] += level;
                    minDist = Math.min(minDist, dist[x][y]);

                    queue.offer(new int[]{x,y});
                }
            }
            level++;
        }

        return minDist;
    }
}