Walls and Gates

Problem

Each cell is INF (empty room), -1 (wall), or 0 (gate). Fill every empty room with the distance to its nearest gate.

Constraints

• 1 ≤ rows, cols ≤ 250

Approach — Graphs

This is a Graphs problem. The idea: explore the graph with BFS or DFS, marking nodes visited so you never process one twice. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(V + E) time.

Solution code

Python

class Solution:
    def wallsAndGates(self, rooms):
        from collections import deque
        if not rooms:
            return rooms
        m, n = len(rooms), len(rooms[0])
        q = deque((i, j) for i in range(m) for j in range(n) if rooms[i][j] == 0)
        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 < m and 0 <= nc < n and rooms[nr][nc] == 2147483647:
                    rooms[nr][nc] = rooms[r][c] + 1
                    q.append((nr, nc))
        return rooms

Java

import java.util.*;
class Solution {
    public void wallsAndGates(int[][] rooms) {
        int m = rooms.length, n = rooms[0].length;
        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.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 nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr < 0 || nc < 0 || nr >= m || nc >= n || rooms[nr][nc] != Integer.MAX_VALUE) continue;
                rooms[nr][nc] = rooms[cur[0]][cur[1]] + 1;
                q.offer(new int[]{nr, nc});
            }
        }
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.