What pattern does Walls and Gates use?

The Pattern: BFS (Multi-Source Traversal) The Heuristic: When multiple sources influence shortest paths simultaneously, enqueue all sources at once and perform BFS to propagate distances in waves, ensuring each node is assigned the shortest distance from any source without redundant searches.

Walls and Gates — BFS

Q: What is the time complexity of Walls and Gates?

O(m * n). Each cell is enqueued and processed at most once during BFS. Since the grid has m rows and n columns, the total operations are proportional to m*n.

Problem

Given a 2D grid rooms representing rooms, gates, and walls, fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, leave it as INF.

m == rooms.length
n == rooms[i].length
1 ≤ m, n ≤ 250
rooms[i][j] is −1, 0, or 2147483647

Example

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]]

The algorithm starts by locating all gates (cells with value 0) and enqueues their positions. It then performs a breadth-first search (BFS) from all gates simultaneously, propagating distance values outward. Each empty room is updated with the shortest distance to any gate encountered during the BFS. Walls (-1) are never updated or traversed. The critical moment is when the BFS expands from multiple gates in parallel, ensuring the shortest distance is assigned to each room without redundant searches.

Approach

Straightforward Solution

A naive approach would run BFS or DFS from each gate separately to update distances, resulting in O(m*n*k) time where k is the number of gates, which is inefficient for large grids.

Core Observation

The shortest distance from any empty room to the nearest gate can be found by simultaneously exploring all gates outward in waves. This is a classic shortest path problem on a grid with uniform edge weights, naturally suited for BFS.

Path to Optimal

Preview

The key insight is to treat all gates as sources in a single multi-source BFS. By enqueuing all gates initially and expanding outward in layers, each empty room is assigned the shortest distance to the closest gate in a single pass…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize a queue with all gate positions and a visited set to track processed cells. Perform BFS layer by layer, updating the distance for each empty room when first visited…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(m * n)

Each cell is enqueued and processed at most once during BFS. Since the grid has m rows and n columns, the total operations are proportional to m*n.

Space

O(m * n)

The queue and visited set can hold up to all cells in the grid in the worst case, resulting in O(m*n) auxiliary space.

Solution

Python

1import collections
2
3class Solution:
  def wallsAndGates(self, rooms: list[list[int]]) -> None:
      ROWS, COLS = len(rooms), len(rooms[0])
      visit = set()
      q = collections.deque()
8
      for r in range(ROWS):
          for c in range(COLS):
              if rooms[r][c] == 0:
                  q.append([r, c])
                  visit.add((r, c))
      
      dist = 0
      while q:
          for i in range(len(q)):
              r, c = q.popleft()
              rooms[r][c] = dist
              
              add_room(r + 1, c)
              add_room(r - 1, c)
              add_room(r, c + 1)
              add_room(r, c - 1)
          dist += 1
26
      def add_room(r, c):
          if (r < 0 or r == ROWS or c < 0 or c == COLS or
              (r, c) in visit or rooms[r][c] == -1):
              return
          visit.add((r, c))
          q.append([r, c])

Step-by-Step Solution

1

Collect All Gates as BFS Starting Points

5ROWS, COLS = len(rooms), len(rooms[0])
6visit = set()
7q = collections.deque()
9for r in range(ROWS):
10    for c in range(COLS):
11        if rooms[r][c] == 0:
12            q.append([r, c])
13            visit.add((r, c))

Objective

To identify all gates in the grid and enqueue their positions as starting points for BFS.

Key Insight

By scanning the entire grid once and enqueuing all gates, the algorithm sets up a multi-source BFS. This simultaneous start from all gates allows distances to propagate outward in waves, ensuring that each empty room is assigned the shortest distance to any gate efficiently.

Interview Quick-Check

Core Logic

Enqueuing all gates initially transforms the problem into a multi-source BFS, enabling shortest distance propagation from all gates in parallel.

State & Boundaries

The visited set prevents revisiting cells and infinite loops during BFS.

Common Pitfalls & Bugs

Forgetting to mark gates as visited when enqueuing them can cause redundant processing or incorrect distance updates.

2

Perform BFS to Update Distances Layer by Layer

To propagate distance values from gates to empty rooms by processing the BFS queue in layers, updating each room's distance with the current BFS level.

3

Expand BFS Frontier by Adding Valid Neighboring Rooms

To add valid neighboring cells to the BFS queue if they are within bounds, not walls, and not yet visited.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 6 Critical lines interviewers watch for.

Line 11 Critical

if rooms[r][c] == 0:

Check if the current cell is a gate (value 0).

Identifying gates is critical because BFS starts from these cells to propagate distances.

Line 12 Critical

q.append([r, c])

Add the gate's coordinates to the BFS queue.

Enqueuing all gates initially sets up the multi-source BFS, enabling simultaneous distance propagation.

Line 19 Critical

rooms[r][c] = dist

Update the current cell's distance in the grid.

Assigning the BFS layer number as the distance ensures the shortest distance from the nearest gate is recorded.

Full line-by-line criticality + rationale for all 20 lines available on Pro.

Test Your Understanding

Why does starting BFS from all gates simultaneously guarantee the shortest distance to the nearest gate for each room?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Walls and Gates from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Walls and Gates drill

or drill a free problem

1	`import collections`
2
3	`class Solution:`
4	`def wallsAndGates(self, rooms: list[list[int]]) -> None:`
5	`ROWS, COLS = len(rooms), len(rooms[0])`
6	`visit = set()`
7	`q = collections.deque()`
8
9	`for r in range(ROWS):`
10	`for c in range(COLS):`
11	`if rooms[r][c] == 0:`
12	`q.append([r, c])`
13	`visit.add((r, c))`
14
15	`dist = 0`
16	`while q:`
17	`for i in range(len(q)):`
18	`r, c = q.popleft()`
19	`rooms[r][c] = dist`
20
21	`add_room(r + 1, c)`
22	`add_room(r - 1, c)`
23	`add_room(r, c + 1)`
24	`add_room(r, c - 1)`
25	`dist += 1`
26
27	`def add_room(r, c):`
28	`if (r < 0 or r == ROWS or c < 0 or c == COLS or`
29	`(r, c) in visit or rooms[r][c] == -1):`
30	`return`
31	`visit.add((r, c))`
32	`q.append([r, c])`

5	`ROWS, COLS = len(rooms), len(rooms[0])`
6	`visit = set()`
7	`q = collections.deque()`
9	`for r in range(ROWS):`
10	`for c in range(COLS):`
11	`if rooms[r][c] == 0:`
12	`q.append([r, c])`
13	`visit.add((r, c))`