Log inSign up
mediumLeetCodeNot Started

Walls and Gates

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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: 2147483647 (i.e., 2^31 - 1), which represents an empty room.

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.

Example 1 · Standard 4x4 Grid with 2 Gates:

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] ]
Explanation: The 2D grid is populated in-place with shortest distances from gates at (0,2) and (3,0).

Example 2 · Single Obstacle Grid:

Input: rooms = [[-1]]
Output: [[-1]]
Explanation: A single wall remains unchanged.

Constraints:

  • m == rooms.length
  • n == rooms[i].length
  • 1 <= m, n <= 250
  • rooms[i][j] is -1, 0, or 2147483647

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Breadth-First Search (BFS) for shortest paths in unweighted graphs
  • Queue data structure operations and multi-element initialization
  • 2D Grid 4-directional boundary validation

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the Multi-Source BFS pattern for multi-target shortest distance problems.
  • Understand why level-order traversal from all sources simultaneously guarantees shortest distances.
  • Use INF / in-place values as implicit visited flags to eliminate extra boolean memory.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding shortest path from multiple targets / sources in an unweighted grid.
  • Grid containing obstacles (-1), multiple sources (0), and unvisited destinations (INF).
  • Constraint requires O(M * N) optimal time.

Algorithmic Decision Tree:

  • Whenever finding shortest distance from ANY of multiple targets, use Multi-Source BFS by pushing all targets into the queue at t = 0.
  • Overwrite destination cells directly with distance + 1 to serve both as the result value and the visited flag.

Connected Patterns:

01 Matrix (LeetCode 542)Rotting Oranges (LeetCode 994)Shortest Bridge (LeetCode 934)

1. BFS from Every Empty Room

Intuition

Search outward from each room until hitting a cell with value 0.

Algorithm

  1. Step 1: Iterate through every cell (r, c) in the grid.
  2. Step 2: If rooms[r][c] == 2147483647, launch helper bfs(r, c).
  3. Step 3: Inside BFS, maintain queue and visited set.
  4. Step 4: Pop (currR, currC, dist); if rooms[currR][currC] == 0, record dist and terminate BFS.
  5. Step 5: Overwrite rooms[r][c] with the minimum distance found.

BFS from Every Empty Room Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [(0,0)=INF, (0,3)=INF, (0,2)=GATE, (1,1)=INF, (3,0)=GATE]
Current operationSTEP 1 OF 6
Iterate grid cells
Visual state
Values and pointers at this exact step
pointers
S
INF
0
↑ BFS start
Variables at this step
room
(0,0)
bfsLevel
0
Check / comparison
rooms[0][0] == INF
Decision / next transition
Start BFS from (0,0).
Why this step matters

Iterate grid cells. Find empty room at (0,0) (val INF). Launch independent BFS.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <tuple>
5
6class Solution {
7 const int INF = 2147483647;
8 int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
9public:
10 void wallsAndGates(std::vector<std::vector<int>>& rooms) {
11 if (rooms.empty() || rooms[0].empty()) return;
12 int m = rooms.size(), n = rooms[0].size();
13
14 for (int r = 0; r < m; ++r) {
15 for (int c = 0; c < n; ++c) {
16 if (rooms[r][c] == INF) {
17 std::queue<std::tuple<int, int, int>> q;
18 std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false));
19 q.push({r, c, 0});
20 visited[r][c] = true;
21 int minDist = INF;
22
23 while (!q.empty()) {
24 auto [cr, cc, d] = q.front();
25 q.pop();
26
27 if (rooms[cr][cc] == 0) {
28 minDist = d;
29 break;
30 }
31
32 for (auto& dir : dirs) {
33 int nr = cr + dir[0], nc = cc + dir[1];
34 if (nr >= 0 && nr < m && nc >= 0 && nc < n && rooms[nr][nc] != -1 && !visited[nr][nc]) {
35 visited[nr][nc] = true;
36 q.push({nr, nc, d + 1});
37 }
38 }
39 }
40 rooms[r][c] = minDist;
41 }
42 }
43 }
44 }
45};
46
47int main() {
48 Solution solver;
49 const int INF = 2147483647;
50 std::vector<std::vector<int>> rooms = {
51 {INF, -1, 0, INF},
52 {INF, INF, INF, -1},
53 {INF, -1, INF, -1},
54 {0, -1, INF, INF}
55 };
56 solver.wallsAndGates(rooms);
57 for (const auto& row : rooms) {
58 for (int x : row) std::cout << x << " ";
59 std::cout << "
60";
61 }
62 return 0;
63}

Time & Space Complexity

  • Time complexity: O((M * N)^2) — Time complexity for BFS from Every Empty Room.
  • Space complexity: O(M * N) — Space complexity for BFS from Every Empty Room.

Why Brute Force Doesn't Scale:

With 250x250 cells (62,500 cells), single-room BFS performs up to 62,500 * 62,500 = 3.9 * 109 operations.

Multi-Source BFS does at most 62,500 queue pops, executing in ~15 milliseconds.

2. Single-Source BFS from Each Gate

Intuition

Instead of searching from thousands of empty rooms, start only from the gates.

Algorithm

  1. Step 1: Find all gate coordinates (r, c) where rooms[r][c] == 0.
  2. Step 2: For each gate, start a BFS with distance 0.
  3. Step 3: If rooms[nr][nc] > dist + 1, update rooms[nr][nc] = dist + 1 and enqueue (nr, nc, dist + 1).

Single-Source BFS from Each Gate Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [Gate 1: (0,2), Gate 2: (3,0), rooms updated in passes]
Current operationSTEP 1 OF 6
Collect all gate coordinates: Gate 1 at (0,2) and Gate 2 at (3,0)
Visual state
Values and pointers at this exact step
pointers
S
(0,2)
(3,0)
0
↑ Gate 1
1
Variables at this step
gates
["(0,2)","(3,0)"]
currentGate
(0,2)
Check / comparison
Found 2 gates
Decision / next transition
Run BFS from Gate 1 first.
Why this step matters

Collect all gate coordinates: Gate 1 at (0,2) and Gate 2 at (3,0).

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <tuple>
5
6class Solution {
7 const int INF = 2147483647;
8 int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
9public:
10 void wallsAndGates(std::vector<std::vector<int>>& rooms) {
11 if (rooms.empty() || rooms[0].empty()) return;
12 int m = rooms.size(), n = rooms[0].size();
13
14 for (int r = 0; r < m; ++r) {
15 for (int c = 0; c < n; ++c) {
16 if (rooms[r][c] == 0) {
17 std::queue<std::pair<int, int>> q;
18 q.push({r, c});
19
20 while (!q.empty()) {
21 auto [cr, cc] = q.front();
22 q.pop();
23
24 for (auto& d : dirs) {
25 int nr = cr + d[0], nc = cc + d[1];
26 if (nr >= 0 && nr < m && nc >= 0 && nc < n && rooms[nr][nc] > rooms[cr][cc] + 1) {
27 rooms[nr][nc] = rooms[cr][cc] + 1;
28 q.push({nr, nc});
29 }
30 }
31 }
32 }
33 }
34 }
35 }
36};
37
38int main() {
39 Solution solver;
40 const int INF = 2147483647;
41 std::vector<std::vector<int>> rooms = {
42 {INF, -1, 0, INF},
43 {INF, INF, INF, -1},
44 {INF, -1, INF, -1},
45 {0, -1, INF, INF}
46 };
47 solver.wallsAndGates(rooms);
48 for (const auto& row : rooms) {
49 for (int x : row) std::cout << x << " ";
50 std::cout << "
51";
52 }
53 return 0;
54}

Time & Space Complexity

  • Time complexity: O(G * M * N) — Time complexity for Single-Source BFS from Each Gate.
  • Space complexity: O(M * N) — Space complexity for Single-Source BFS from Each Gate.

3. Multi-Source Simultaneous Level-Order BFS

Intuition

Because BFS progresses level-by-level, the first gate wave to touch an empty room is guaranteed to be the closest.

Algorithm

  1. Step 1: Scan the grid. For every cell where rooms[r][c] == 0, push (r, c) to the BFS queue.
  2. Step 2: While the queue is not empty, pop (r, c).
  3. Step 3: For each of the 4 neighbors (nr, nc):
  4. Step 4: If in bounds and rooms[nr][nc] == 2147483647 (INF):
  5. Step 5: Set rooms[nr][nc] = rooms[r][c] + 1.
  6. Step 6: Push (nr, nc) to the queue.

Multi-Source Simultaneous Level-Order BFS Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [(0,2)=GATE, (3,0)=GATE, (0,3)=1, (1,2)=1, (1,1)=2, (2,2)=2, (0,0)=3]
Current operationSTEP 1 OF 6
Multi-source insight: Push ALL gates into queue at distance 0 simultaneously
Visual state
Values and pointers at this exact step
pointers
S
0
0
0
↑ Gate 1
1
↑ Gate 2
Variables at this step
queue
["(0,2)","(3,0)"]
level
0
Check / comparison
rooms[r][c] == 0
Decision / next transition
Enqueue (0,2) and (3,0). Initial queue size = 2.
Why this step matters

Multi-source insight: Push ALL gates into queue at distance 0 simultaneously.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5class Solution {
6public:
7 void wallsAndGates(std::vector<std::vector<int>>& rooms) {
8 if (rooms.empty() || rooms[0].empty()) return;
9 int m = rooms.size(), n = rooms[0].size();
10 const int INF = 2147483647;
11
12 std::queue<std::pair<int, int>> q;
13 // Phase 1: Enqueue all gates simultaneously
14 for (int r = 0; r < m; ++r) {
15 for (int c = 0; c < n; ++c) {
16 if (rooms[r][c] == 0) {
17 q.push({r, c});
18 }
19 }
20 }
21
22 int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
23
24 // Phase 2: Multi-source outward wave
25 while (!q.empty()) {
26 auto [r, c] = q.front();
27 q.pop();
28
29 for (auto& d : dirs) {
30 int nr = r + d[0], nc = c + d[1];
31 if (nr >= 0 && nr < m && nc >= 0 && nc < n && rooms[nr][nc] == INF) {
32 rooms[nr][nc] = rooms[r][c] + 1;
33 q.push({nr, nc});
34 }
35 }
36 }
37 }
38};
39
40int main() {
41 Solution solver;
42 const int INF = 2147483647;
43 std::vector<std::vector<int>> rooms = {
44 {INF, -1, 0, INF},
45 {INF, INF, INF, -1},
46 {INF, -1, INF, -1},
47 {0, -1, INF, INF}
48 };
49 solver.wallsAndGates(rooms);
50 std::cout << "Walls and Gates Result Matrix:
51";
52 for (const auto& row : rooms) {
53 for (int x : row) std::cout << x << " ";
54 std::cout << "
55";
56 }
57 return 0;
58}

Time & Space Complexity

  • Time complexity: O(M * N) — Time complexity for Multi-Source Simultaneous Level-Order BFS.
  • Space complexity: O(M * N) — Space complexity for Multi-Source Simultaneous Level-Order BFS.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — BFS from Every Empty RoomO((M * N)^2)O(M * N)For every INF cell, initiate a standalone BFS until the first gate (0) is reached.Re-explores identical paths (M*N) times.
2.Better — Single-Source BFS from Each GateO(G * M * N)O(M * N)For each gate, run an independent BFS updating rooms[r][c] = min(rooms[r][c], dist).G independent queue passes.
3.Optimal — Multi-Source Simultaneous BFSOptimalO(M * N)O(M * N)Enqueue all gates initially. Propagate wave in parallel so each cell is visited exactly once.None; theoretical optimum.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • No gates present in grid — Queue remains empty, all INF rooms remain unchanged.
  • No empty rooms (only walls and gates) — Traversal terminates immediately with zero updates.
  • Completely walled-off empty room — Room is never reached by BFS wave and stays INF (2147483647).
  • Grid of size 1x1 — Walls or gate handled in O(1) without indexing out of bounds.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does Multi-Source BFS guarantee finding the shortest distance to any gate?

2.What is the time complexity of the Multi-Source BFS algorithm on an M x N grid?

3.Why do we start BFS simultaneously from all Gates (0) instead of from each empty Room (INF)?

Back to DSA Sheet