Problem

You are given an m x n grid rooms initialized with these three possible values.

  • -1 A wall or an obstacle.
  • 0 A gate.
  • INF Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

Examples

Example 1

$$ \begin{array}{|c|c|c|c|} \hline \colorbox{Turquoise} \infty & -1 & \colorbox{pink} 0 & \colorbox{Turquoise} \infty \\ \hline \colorbox{Turquoise} \infty & \colorbox{Turquoise} \infty & \colorbox{Turquoise} \infty & -1 \\ \hline \colorbox{Turquoise} \infty & -1 & \colorbox{Turquoise} \infty & -1 \\ \hline \colorbox{pink} 0 & -1 & \colorbox{Turquoise} \infty & \colorbox{Turquoise} \infty \\ \hline \end{array} $$

1
2

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Given the 2D grid, After running your function, the 2D grid should be:

1
2
3
4

 3  -1   0   1
 2   2   1  -1
 1  -1   2  -1
 0  -1   3   4

Looking at above example as wall and gate:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input:
_ W G _
_ _ _ W
_ W _ W
G W _ _

Output:
3 W G 1
2 2 1 W
1 W 2 W
G W 3 4

Example 2

1
2

Input: rooms = [[-1]]
Output: [[-1]]

Solution

Understanding the Problem

It is a classic backtracking problem. We can start from each gate (0 point) and search for its neighbors. We can use either DFS or BFS for the solution.

We first find all the positions of the gates (val=0), and then backtrack to all possible empty spaces (val=INF), updating the value of the empty space cells to the minimum distance to the nearest gate.

This can be done using a simple BFS, updating the paths similarly to Dijkstra’s shortest path problem, keeping the invariant room[i][j] <= room[r][c]+1, where room[i][j] is a neighbor empty space and room[r][c] is the current position of a node on a path to escape. It is important to know where the walls are and prune the search tree from the position where a wall is discovered (val=-1).

Method 1 – DFS from Each Gate

Intuition

The key idea is to treat each gate (cell with value 0) as a starting point and use DFS to propagate the minimum distance to all reachable empty rooms (INF). We only update a room if the new distance is less than its current value, ensuring the shortest path from any gate is recorded.

Approach

  1. Iterate through the grid to find all gates (0).
  2. For each gate, start a DFS with distance 0.
  3. In DFS:
    • If out of bounds, or at a wall (-1), or the current distance is not better, return. We do not need an explicit visited set in this DFS approach. This is because we only recurse into a cell if the new distance is less than its current value. Once a cell has been updated with the shortest distance from any gate, future DFS calls with a greater or equal distance will not proceed further, effectively preventing cycles and redundant work.
    • Update the room with the current distance.
    • Recursively call DFS for all four directions (up, down, left, right) with distance + 1.
  4. Repeat for all gates.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        int m = rooms.size(), n = rooms[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (rooms[i][j] == 0) dfs(rooms, i, j, 0);
            }
        }
    }
    void dfs(vector<vector<int>>& rooms, int i, int j, int dist) {
        int m = rooms.size(), n = rooms[0].size();
        if (i < 0 || i >= m || j < 0 || j >= n || rooms[i][j] < dist) return;
        rooms[i][j] = dist;
        dfs(rooms, i+1, j, dist+1);
        dfs(rooms, i-1, j, dist+1);
        dfs(rooms, i, j+1, dist+1);
        dfs(rooms, i, j-1, dist+1);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

type Solution struct{}
func (Solution) wallsAndGates(rooms [][]int) {
    m, n := len(rooms), len(rooms[0])
    var dfs func(i, j, d int)
    dfs = func(i, j, d int) {
        if i < 0 || i >= m || j < 0 || j >= n || rooms[i][j] < d { return }
        rooms[i][j] = d
        dfs(i+1, j, d+1)
        dfs(i-1, j, d+1)
        dfs(i, j+1, d+1)
        dfs(i, j-1, d+1)
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if rooms[i][j] == 0 {
                dfs(i, j, 0)
            }
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public void wallsAndGates(int[][] rooms) {
        int m = rooms.length, n = rooms[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) {
                    dfs(rooms, i, j, 0);
                }
            }
        }
    }
    private void dfs(int[][] rooms, int i, int j, int dist) {
        int m = rooms.length, n = rooms[0].length;
        if (i < 0 || i >= m || j < 0 || j >= n || rooms[i][j] < dist) return;
        rooms[i][j] = dist;
        dfs(rooms, i+1, j, dist+1);
        dfs(rooms, i-1, j, dist+1);
        dfs(rooms, i, j+1, dist+1);
        dfs(rooms, i, j-1, dist+1);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun wallsAndGates(rooms: Array<IntArray>) {
        val m = rooms.size
        val n = rooms[0].size
        fun dfs(i: Int, j: Int, d: Int) {
            if (i !in 0 until m || j !in 0 until n || rooms[i][j] < d) return
            rooms[i][j] = d
            dfs(i+1, j, d+1)
            dfs(i-1, j, d+1)
            dfs(i, j+1, d+1)
            dfs(i, j-1, d+1)
        }
        for (i in 0 until m) for (j in 0 until n) if (rooms[i][j] == 0) dfs(i, j, 0)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def wallsAndGates(self, rooms: list[list[int]]) -> None:
        m, n = len(rooms), len(rooms[0])
        def dfs(i: int, j: int, d: int):
            if i < 0 or i >= m or j < 0 or j >= n or rooms[i][j] < d:
                return
            rooms[i][j] = d
            dfs(i+1, j, d+1)
            dfs(i-1, j, d+1)
            dfs(i, j+1, d+1)
            dfs(i, j-1, d+1)
        for i in range(m):
            for j in range(n):
                if rooms[i][j] == 0:
                    dfs(i, j, 0)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn walls_and_gates(rooms: &mut Vec<Vec<i32>>) {
        let m = rooms.len();
        let n = rooms[0].len();
        fn dfs(rooms: &mut Vec<Vec<i32>>, i: i32, j: i32, d: i32, m: i32, n: i32) {
            if i < 0 || i >= m || j < 0 || j >= n || rooms[i as usize][j as usize] < d { return; }
            rooms[i as usize][j as usize] = d;
            dfs(rooms, i+1, j, d+1, m, n);
            dfs(rooms, i-1, j, d+1, m, n);
            dfs(rooms, i, j+1, d+1, m, n);
            dfs(rooms, i, j-1, d+1, m, n);
        }
        for i in 0..m {
            for j in 0..n {
                if rooms[i][j] == 0 {
                    dfs(rooms, i as i32, j as i32, 0, m as i32, n as i32);
                }
            }
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    wallsAndGates(rooms: number[][]): void {
        const m = rooms.length, n = rooms[0].length;
        const dfs = (i: number, j: number, d: number) => {
            if (i < 0 || i >= m || j < 0 || j >= n || rooms[i][j] < d) return;
            rooms[i][j] = d;
            dfs(i+1, j, d+1);
            dfs(i-1, j, d+1);
            dfs(i, j+1, d+1);
            dfs(i, j-1, d+1);
        };
        for (let i = 0; i < m; i++)
            for (let j = 0; j < n; j++)
                if (rooms[i][j] === 0) dfs(i, j, 0);
    }
}

Complexity

  • ⏰ Time complexity: O(mn) — Each cell is visited at most once for each gate, but since we only update if the new distance is smaller, the total work is proportional to the number of cells.
  • 🧺 Space complexity: O(mn) — For recursion stack in the worst case (all empty rooms).

Method 2 - Multi-Source BFS from All Gates

Intuition

Instead of running a search from every empty room, we can treat all gates (0 cells) as sources and perform a breadth-first search (BFS) simultaneously from all of them. This way, each empty room is filled with the shortest distance to any gate, and we avoid redundant work.

Approach

  1. Initialize a queue and enqueue all gate positions (rooms[i][j] == 0).
  2. For each position in the queue, pop it and check its four neighbors (up, down, left, right).
  3. If a neighbor is an empty room (INF), update its value to the current cell’s value + 1 and enqueue it.
  4. Repeat until the queue is empty.

This approach ensures that each room is updated with the shortest distance to a gate, as BFS explores all nodes at distance d before nodes at distance d+1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        int m = rooms.size(), n = rooms[0].size();
        queue<pair<int, int>> q;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (rooms[i][j] == 0) q.push({i, j});
        vector<pair<int, int>> dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.empty()) {
            auto [i, j] = q.front(); q.pop();
            for (auto [di, dj] : dirs) {
                int ni = i + di, nj = j + dj;
                if (ni < 0 || ni >= m || nj < 0 || nj >= n || rooms[ni][nj] != INT_MAX) continue;
                rooms[ni][nj] = rooms[i][j] + 1;
                q.push({ni, nj});
            }
        }
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

type pair struct{ x, y int }
func wallsAndGates(rooms [][]int) {
    m, n := len(rooms), len(rooms[0])
    q := []pair{}
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if rooms[i][j] == 0 {
                q = append(q, pair{i, j})
            }
        }
    }
    dirs := [][2]int{{1,0},{-1,0},{0,1},{0,-1}}
    for len(q) > 0 {
        p := q[0]; q = q[1:]
        for _, d := range dirs {
            ni, nj := p.x+d[0], p.y+d[1]
            if ni < 0 || ni >= m || nj < 0 || nj >= n || rooms[ni][nj] != 2147483647 { continue }
            rooms[ni][nj] = rooms[p.x][p.y] + 1
            q = append(q, pair{ni, nj})
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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[] cell = q.poll();
            int i = cell[0], j = cell[1];
            for (int[] d : dirs) {
                int ni = i + d[0], nj = j + d[1];
                if (ni < 0 || ni >= m || nj < 0 || nj >= n || rooms[ni][nj] != Integer.MAX_VALUE) continue;
                rooms[ni][nj] = rooms[i][j] + 1;
                q.offer(new int[]{ni, nj});
            }
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun wallsAndGates(rooms: Array<IntArray>) {
        val m = rooms.size
        val n = rooms[0].size
        val q = ArrayDeque<Pair<Int, Int>>()
        for (i in 0 until m) for (j in 0 until n) if (rooms[i][j] == 0) q.add(i to j)
        val dirs = listOf(1 to 0, -1 to 0, 0 to 1, 0 to -1)
        while (q.isNotEmpty()) {
            val (i, j) = q.removeFirst()
            for ((di, dj) in dirs) {
                val ni = i + di; val nj = j + dj
                if (ni !in 0 until m || nj !in 0 until n || rooms[ni][nj] != Int.MAX_VALUE) continue
                rooms[ni][nj] = rooms[i][j] + 1
                q.add(ni to nj)
            }
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def wallsAndGates(self, rooms: list[list[int]]) -> None:
        from collections import deque
        m, n = len(rooms), len(rooms[0])
        q = deque()
        for i in range(m):
            for j in range(n):
                if rooms[i][j] == 0:
                    q.append((i, j))
        dirs = [(1,0),(-1,0),(0,1),(0,-1)]
        while q:
            i, j = q.popleft()
            for di, dj in dirs:
                ni, nj = i+di, j+dj
                if 0 <= ni < m and 0 <= nj < n and rooms[ni][nj] == 2147483647:
                    rooms[ni][nj] = rooms[i][j] + 1
                    q.append((ni, nj))
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

use std::collections::VecDeque;
impl Solution {
    pub fn walls_and_gates(rooms: &mut Vec<Vec<i32>>) {
        let m = rooms.len();
        let n = rooms[0].len();
        let mut q = VecDeque::new();
        for i in 0..m {
            for j in 0..n {
                if rooms[i][j] == 0 {
                    q.push_back((i, j));
                }
            }
        }
        let dirs = [(1,0),(-1,0),(0,1),(0,-1)];
        while let Some((i, j)) = q.pop_front() {
            for (di, dj) in dirs.iter() {
                let ni = i as i32 + di;
                let nj = j as i32 + dj;
                if ni < 0 || ni >= m as i32 || nj < 0 || nj >= n as i32 { continue; }
                let (ni, nj) = (ni as usize, nj as usize);
                if rooms[ni][nj] == i32::MAX {
                    rooms[ni][nj] = rooms[i][j] + 1;
                    q.push_back((ni, nj));
                }
            }
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    wallsAndGates(rooms: number[][]): void {
        const m = rooms.length, n = rooms[0].length;
        const q: [number, number][] = [];
        for (let i = 0; i < m; i++)
            for (let j = 0; j < n; j++)
                if (rooms[i][j] === 0) q.push([i, j]);
        const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
        while (q.length) {
            const [i, j] = q.shift()!;
            for (const [di, dj] of dirs) {
                const ni = i + di, nj = j + dj;
                if (ni < 0 || ni >= m || nj < 0 || nj >= n || rooms[ni][nj] !== 2147483647) continue;
                rooms[ni][nj] = rooms[i][j] + 1;
                q.push([ni, nj]);
            }
        }
    }
}

Complexity

  • ⏰ Time complexity: O(mn) — Each cell is visited at most once, and each edge is checked at most once.
  • 🧺 Space complexity: O(mn) — For the queue in the worst case (all empty rooms).