Walls and Gates
Walls and Gates is a medium graphs problem solved with the multi source bfs pattern.
The best approach, optimal (multi-source bfs from all gates), runs in O(m · n) time and O(m · n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (bfs from each gate) up.
Problem
You are given an m x n grid rooms where each cell is one of:
-1: a wall you cannot pass through,0: a gate,2147483647: an empty room (this value stands for “infinitely far”).
Fill in place every empty room with the number of steps to its nearest gate, moving up, down, left or right one cell per step and never through walls. A room that cannot reach any gate keeps the value 2147483647. The function returns nothing; the grid itself is checked afterwards.
Examples
Example 1
- Input
rooms = [[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]- Output
[[2,-1,0],[1,2,1],[0,-1,2]]- Why
- Each empty room now holds the number of steps to the closest of the two gates, walking around the walls.
Example 2
- Input
rooms = [[0,2147483647],[-1,-1],[2147483647,2147483647]]- Output
[[0,1],[-1,-1],[2147483647,2147483647]]- Why
- The bottom row is cut off by walls, so those rooms cannot reach any gate and keep the value 2147483647.
Constraints
1 <= m, n <= 250where the grid has m rows and n columns.- Every cell is
-1(wall),0(gate) or2147483647(empty room).
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (BFS from each gate) | O(g · m · n) | O(m · n) |
| Optimal (multi-source BFS from all gates) | O(m · n) | O(m · n) |
1Brute force (BFS from each gate)
O(g · m · n)Each of the g gates may explore the whole grid.O(m · n)The visited matrix and the queue of one BFS.Run a separate BFS from every gate. Each search walks over the empty rooms and writes the smaller of the stored value and its own distance into each room it reaches. After all gates are processed, every room holds the distance to its closest gate.
- For each gate (i, j), BFS with a fresh visited matrix, tracking the distance of each level.
- When a room is reached at distance d, set rooms[r][c] = min(rooms[r][c], d).
- Walls and gates are never entered.
class Solution {
public void wallsAndGates(int[][] rooms) {
int m = rooms.length, n = rooms[0].length;
int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (rooms[i][j] != 0) continue;
boolean[][] seen = new boolean[m][n];
ArrayDeque<int[]> q = new ArrayDeque<>();
q.add(new int[] { i, j, 0 });
seen[i][j] = true;
while (!q.isEmpty()) {
int[] c = q.poll();
for (int[] d : dirs) {
int r = c[0] + d[0], s = c[1] + d[1];
if (r < 0 || r >= m || s < 0 || s >= n || seen[r][s] || rooms[r][s] <= 0) continue;
seen[r][s] = true;
rooms[r][s] = Math.min(rooms[r][s], c[2] + 1);
q.add(new int[] { r, s, c[2] + 1 });
}
}
}
}
}
}class Solution:
def wallsAndGates(self, rooms: List[List[int]]) -> None:
m, n = len(rooms), len(rooms[0])
for i in range(m):
for j in range(n):
if rooms[i][j] != 0:
continue
seen = [[False] * n for _ in range(m)]
seen[i][j] = True
q = deque([(i, j, 0)])
while q:
r, s, d = q.popleft()
for dr, ds in ((1, 0), (-1, 0), (0, 1), (0, -1)):
a, b = r + dr, s + ds
if 0 <= a < m and 0 <= b < n and not seen[a][b] and rooms[a][b] > 0:
seen[a][b] = True
rooms[a][b] = min(rooms[a][b], d + 1)
q.append((a, b, d + 1))class Solution {
public:
void wallsAndGates(vector<vector<int>>& rooms) {
int m = rooms.size(), n = rooms[0].size();
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (rooms[i][j] != 0) continue;
vector<vector<bool>> seen(m, vector<bool>(n, false));
queue<array<int, 3>> q;
q.push({i, j, 0});
seen[i][j] = true;
while (!q.empty()) {
auto [r, s, d] = q.front();
q.pop();
for (auto& dir : dirs) {
int a = r + dir[0], b = s + dir[1];
if (a < 0 || a >= m || b < 0 || b >= n || seen[a][b] || rooms[a][b] <= 0) continue;
seen[a][b] = true;
rooms[a][b] = min(rooms[a][b], d + 1);
q.push({a, b, d + 1});
}
}
}
}
}
};function wallsAndGates(rooms) {
const m = rooms.length, n = rooms[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (rooms[i][j] !== 0) continue;
const seen = Array.from({ length: m }, () => new Array(n).fill(false));
seen[i][j] = true;
const q = [[i, j, 0]];
for (let h = 0; h < q.length; h++) {
const [r, s, d] = q[h];
for (const [dr, ds] of dirs) {
const a = r + dr, b = s + ds;
if (a < 0 || a >= m || b < 0 || b >= n || seen[a][b] || rooms[a][b] <= 0) continue;
seen[a][b] = true;
rooms[a][b] = Math.min(rooms[a][b], d + 1);
q.push([a, b, d + 1]);
}
}
}
}
}2Optimal (multi-source BFS from all gates)
O(m · n)Every cell enters the queue at most once and checks 4 neighbours.O(m · n)The queue can hold a large part of the grid.Start one BFS with every gate in the queue. BFS expands in rings of equal distance, so the first time a room is reached it is reached from its nearest gate. An empty room still holding 2147483647 is unvisited; once it gets a distance it is never touched again.
- Push every gate cell into the queue.
- Pop a cell; for each neighbour that is still an empty room (value 2147483647), set it to the cell's value + 1 and push it.
- Stop when the queue is empty; unreachable rooms keep 2147483647.
class Solution {
public void wallsAndGates(int[][] rooms) {
final int EMPTY = Integer.MAX_VALUE;
int m = rooms.length, n = rooms[0].length;
int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
ArrayDeque<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 });
while (!q.isEmpty()) {
int[] c = q.poll();
for (int[] d : dirs) {
int r = c[0] + d[0], s = c[1] + d[1];
if (r < 0 || r >= m || s < 0 || s >= n || rooms[r][s] != EMPTY) continue;
rooms[r][s] = rooms[c[0]][c[1]] + 1;
q.add(new int[] { r, s });
}
}
}
}class Solution:
def wallsAndGates(self, rooms: List[List[int]]) -> None:
EMPTY = 2147483647
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, s = q.popleft()
for dr, ds in ((1, 0), (-1, 0), (0, 1), (0, -1)):
a, b = r + dr, s + ds
if 0 <= a < m and 0 <= b < n and rooms[a][b] == EMPTY:
rooms[a][b] = rooms[r][s] + 1
q.append((a, b))class Solution {
public:
void wallsAndGates(vector<vector<int>>& rooms) {
const int EMPTY = INT_MAX;
int m = rooms.size(), n = rooms[0].size();
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
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});
while (!q.empty()) {
auto [r, s] = q.front();
q.pop();
for (auto& d : dirs) {
int a = r + d[0], b = s + d[1];
if (a < 0 || a >= m || b < 0 || b >= n || rooms[a][b] != EMPTY) continue;
rooms[a][b] = rooms[r][s] + 1;
q.push({a, b});
}
}
}
};function wallsAndGates(rooms) {
const EMPTY = 2147483647;
const m = rooms.length, n = rooms[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const q = [];
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
if (rooms[i][j] === 0) q.push([i, j]);
for (let h = 0; h < q.length; h++) {
const [r, s] = q[h];
for (const [dr, ds] of dirs) {
const a = r + dr, b = s + ds;
if (a < 0 || a >= m || b < 0 || b >= n || rooms[a][b] !== EMPTY) continue;
rooms[a][b] = rooms[r][s] + 1;
q.push([a, b]);
}
}
}Edge cases to test
- No gates at all: nothing changes
- Rooms walled off from every gate keep 2147483647
- Several gates, where each room must take the closest one
- A grid with a single cell
Hints
Hint 1
The distance from a room to a gate is a shortest path in an unweighted grid, which is exactly what BFS computes.
Hint 2
Running one search per room or per gate repeats a lot of work. Can all gates start searching at the same time?
Hint 3
Put every gate in the queue at distance 0. The first time BFS reaches a room, it came from the nearest gate.
FAQ
What is the best time complexity for Walls and Gates?
Optimal (multi-source BFS from all gates) runs in O(m · n) time and O(m · n) extra space. Every cell enters the queue at most once and checks 4 neighbours.
Which pattern does Walls and Gates use?
It is a graphs problem that uses the multi source bfs pattern. Other problems with the same pattern: Rotting Oranges, 01 Matrix, Pacific Atlantic Water Flow.
Is there a brute force solution for Walls and Gates?
Yes. Brute force (BFS from each gate) takes O(g · m · n) time and O(m · n) space. Run a separate BFS from every gate.
Which edge cases should I test for Walls and Gates?
No gates at all: nothing changes; Rooms walled off from every gate keep 2147483647; Several gates, where each room must take the closest one; A grid with a single cell.