class Solution {
    
    private void collectGatesLocation(int[][] rooms, Queue<int[]> queue, int m, int n, boolean[][] visited){
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(rooms[i][j] == 0){
                    visited[i][j] = true;
                    queue.add(new int[]{i, j});
                }
            }
        }
    }
    
    private void exploreNeighbors(int x, int y, int[][] rooms, boolean[][] visited, Queue<int[]> queue, int m, int n){
        int[][] directions = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
        for(int[] direction: directions){
            int newX = x + direction[0];
            int newY = y + direction[1];
            if(newX < 0 || newX >= m || newY < 0 || newY >= n || rooms[newX][newY] == -1 || visited[newX][newY]){
                continue;
            }
            visited[newX][newY] = true;
            queue.add(new int[]{newX, newY});
        }
    }
    
    public void wallsAndGates(int[][] rooms) {
        // we use bfs to calculate the shortest distancde from an empty room to the gate
        // why normal bfs won't work? - let say if we start bfs from one of the gate and update
        // the distance of its neighbouring empty rooms with respect to the given gate, it might not
        // be the shortest distance possible. There is a possibility that we can reach to that empty root
        // from another gate which is closed to the current gate.
        // Solution - we need to start our bfs search from all the gates at a single time and keep distance 
        // of the empty rooms in parallel. This way we can be sure that whatever distance we fill into the 
        // empty room is the shortest distance. We update the cell only if its an empty cell.
        
        int m = rooms.length;
        int n = rooms[0].length;
        
        // first we need to get the coordinates of all the gates and visit them
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        collectGatesLocation(rooms, queue, m, n, visited);
        
        // now we start bfs from all the gates in parallel
        int distance = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            // in this iteration, we process all those cells which are 'distance' units away from gates
            for(int i=0; i<size; i++){
                int[] curr = queue.poll();
                int x = curr[0];
                int y = curr[1];
                // we first update the distance of the current cell from the gate and then explore its neighbors
                rooms[x][y] = distance;
                exploreNeighbors(x, y, rooms, visited, queue, m, n);
            }
            distance++;
        }
        return;
    }
}