Walls and Gates (Matrix)

Fill each empty room (INF) in a matrix with the distance to its nearest gate (0). Walls are -1.

Example 1

Multi-source BFS from all gates simultaneously

Solution Approach

Multi-source BFS starting from all gate (0) positions. Each BFS level adds 1 to the distance.

Enqueue all gate positions.
BFS: for each cell, update 4-directional INF neighbors with distance+1.

Java

import java.util.*;

class Solution {
    public void wallsAndGates(int[][] rooms) {
        int m=rooms.length, n=rooms[0].length;
        Queue<int[]> q=new LinkedList<>();
        for (int i=0;i<m;i++) for (int j=0;j<n;j++) if (rooms[i][j]==0) q.offer(new int[]{i,j});
        int[][] dirs={{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.isEmpty()){
            int[] cur=q.poll();
            for (int[] d:dirs){int r=cur[0]+d[0],c=cur[1]+d[1];
                if(r>=0&&r<m&&c>=0&&c<n&&rooms[r][c]==Integer.MAX_VALUE){
                    rooms[r][c]=rooms[cur[0]][cur[1]]+1; q.offer(new int[]{r,c});}}
        }
    }
}

Time Complexity: O(M*N)
Space Complexity: O(M*N)