203. Walls and Gates

Start BFS from every gate at once. The first time BFS reaches an empty room, it does so along the shortest path, so that room's distance is final.

BFS from every gate simultaneously

Seed the queue with all gates (value 0). BFS outward: whenever a neighbouring empty room (still INF) is reached, set it to the current distance + 1 and enqueue it. Because all gates expand together layer by layer, each room is filled with its true nearest-gate distance the first time it's touched.

queue = all gate cells
while queue:
    r,c = pop
    for empty neighbour: rooms[nb] = rooms[r][c] + 1; enqueue

Walls (-1) and unreachable rooms are never updated.

Complexity

• Time: O(m·n).
• Space: O(m·n).

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public int[][] wallsAndGates(int[][] rooms) {
        if (rooms.length == 0 || rooms[0].length == 0) return rooms;
        int m = rooms.length, n = rooms[0].length;
        int INF = 2147483647;
        Queue<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) q.add(new int[]{i, j});
            }
        }
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int r = cur[0], c = cur[1];
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && rooms[nr][nc] == INF) {
                    rooms[nr][nc] = rooms[r][c] + 1;
                    q.add(new int[]{nr, nc});
                }
            }
        }
        return rooms;
    }
}