Walls and Gates — Multi-Source BFS from Gates

Problem

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

Approach

Same as 01-Matrix but source is gates (0). Push all gates, BFS outward updating empty rooms.

Time: O(mn) | Space: O(mn)

Solutions

Python

from collections import deque
INF = 2**31 - 1
class Solution:
    def wallsAndGates(self, rooms: list[list[int]]) -> None:
        R,C=len(rooms),len(rooms[0])
        q=deque()
        for r in range(R):
            for c in range(C):
                if rooms[r][c]==0: q.append((r,c))
        while q:
            r,c=q.popleft()
            for dr,dc in[(1,0),(-1,0),(0,1),(0,-1)]:
                nr,nc=r+dr,c+dc
                if 0<=nr<R and 0<=nc<C and rooms[nr][nc]==INF:
                    rooms[nr][nc]=rooms[r][c]+1; q.append((nr,nc))

Java

class Solution {
    public void wallsAndGates(int[][] rooms) {
        int R=rooms.length,C=rooms[0].length,INF=Integer.MAX_VALUE;
        Queue<int[]> q=new LinkedList<>();
        for(int r=0;r<R;r++) for(int c=0;c<C;c++)
            if(rooms[r][c]==0) q.add(new int[]{r,c});
        int[][] dirs={{0,1},{0,-1},{1,0},{-1,0}};
        while(!q.isEmpty()){
            int[] cur=q.poll();
            for(int[] d:dirs){
                int nr=cur[0]+d[0],nc=cur[1]+d[1];
                if(nr>=0&&nr<R&&nc>=0&&nc<C&&rooms[nr][nc]==INF){
                    rooms[nr][nc]=rooms[cur[0]][cur[1]]+1;
                    q.add(new int[]{nr,nc});
                }
            }
        }
    }
}

Complexity

Time: O(mn) | Space: O(mn)