Walls And Gates: the idea to remember.

The core insight

Queue all gates at distance zero and assign empty rooms when they are first reached.

Why it works

Breadth first expansion from all gates reaches each room by its shortest available path.

The mistake to avoid

Do not launch an independent search per room. Mark rooms before enqueueing to avoid repeated work.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Queue all gates at distance zero and assign empty rooms when they are first reached.
public void wallsAndGates(int[][] rooms) {
    Queue<int[]> q = new LinkedList<>();
    int m = rooms.length;
    int n = rooms[0].length;
    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 });
        }
    }
    if (q.size() == 0) return;
    int[][] dirs = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int row = cur[0];
        int col = cur[1];
        for (int[] dir : dirs) {
            int x = row + dir[0];
            int y = col + dir[1];
            if (
                x >= m ||
                y >= n ||
                x < 0 ||
                y < 0 ||
                rooms[x][y] != Integer.MAX_VALUE
            ) continue;
            q.add(new int[] { x, y });


            rooms[x][y] = rooms[row][col] + 1;

        }
    }
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection