Approach

Walls and Gates

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 - Infinity (2147483647) means 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.

Examples

Example 1:

Input:

rooms = [
  [INF, -1,  0,  INF],
  [INF, INF, INF, -1 ],
  [INF, -1,  INF, -1 ],
  [0,   -1,  INF, INF]
]

Output:

[
  [3, -1, 0, 1],
  [2,  2, 1, -1],
  [1, -1, 2, -1],
  [0, -1, 3, 2]
]

Example 2:

Input:

rooms = [[-1]]

Output:

[[-1]]

Example 3:

Input:

rooms = [[0]]

Output:

[[0]]

Approach: Multi-Source BFS

The key insight is to use multi-source Breadth-First Search (BFS) starting from all gates simultaneously. This ensures that each room gets the shortest distance to any gate.

Algorithm Steps:

Initialize: Find all gates (cells with value 0) and add them to a queue
Multi-Source BFS: Process the queue level by level:
- For each cell in the current level
- Check all 4 neighbors (up, down, left, right)
- If a neighbor is an empty room (value = INF), update its distance
- Add the neighbor to the queue for the next level
Distance Tracking: Each level represents an increment in distance from the gates

Why BFS Works:

BFS guarantees the shortest path in unweighted graphs
Starting from all gates simultaneously ensures each room gets the minimum distance
Level-by-level processing naturally increments the distance by 1

Time Complexity: O(m × n)

We visit each cell at most once
Each cell is processed only when it's an empty room

Space Complexity: O(m × n)

Queue can contain up to all cells in worst case
We modify the input grid in-place

Key Points

This is a classic multi-source BFS problem
In-place modification saves space
Distance values naturally increase level by level
Unreachable rooms remain at INF

Solution

java

1class Solution {
2    private static final int INF = 2147483647;
3    private static final int WALL = -1;
4    private static final int GATE = 0;
5    private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
6
7    public void wallsAndGates(int[][] rooms) {
8        if (rooms == null || rooms.length == 0 || rooms[0].length == 0) {
9            return;
10        }
11
12        int m = rooms.length;
13        int n = rooms[0].length;
14        Queue<int[]> queue = new LinkedList<>();
15
16        // Step 1: Find all gates and add to queue
17        for (int i = 0; i < m; i++) {
18            for (int j = 0; j < n; j++) {
19                if (rooms[i][j] == GATE) {
20                    queue.offer(new int[]{i, j});
21                }
22            }
23        }
24
25        // Step 2: Multi-source BFS
26        while (!queue.isEmpty()) {
27            int[] curr = queue.poll();
28            int row = curr[0];
29            int col = curr[1];
30
31            // Check all 4 directions
32            for (int[] dir : DIRECTIONS) {
33                int newRow = row + dir[0];
34                int newCol = col + dir[1];
35
36                // Check bounds and if it's an empty room
37                if (newRow >= 0 && newRow < m &&
38                    newCol >= 0 && newCol < n &&
39                    rooms[newRow][newCol] == INF) {
40
41                    // Update distance (current cell's distance + 1)
42                    rooms[newRow][newCol] = rooms[row][col] + 1;
43                    queue.offer(new int[]{newRow, newCol});
44                }
45            }
46        }
47    }
48}
49
50/**
51 * Alternative solution with explicit distance tracking
52 */
53class SolutionWithDistance {
54    public void wallsAndGates(int[][] rooms) {
55        if (rooms == null || rooms.length == 0) return;
56
57        int m = rooms.length;
58        int n = rooms[0].length;
59        Queue<int[]> queue = new LinkedList<>();
60
61        // Add all gates to queue
62        for (int i = 0; i < m; i++) {
63            for (int j = 0; j < n; j++) {
64                if (rooms[i][j] == 0) {
65                    queue.offer(new int[]{i, j});
66                }
67            }
68        }
69
70        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
71        int distance = 0;
72
73        // BFS level by level
74        while (!queue.isEmpty()) {
75            int size = queue.size();
76            distance++;
77
78            for (int i = 0; i < size; i++) {
79                int[] curr = queue.poll();
80                int row = curr[0];
81                int col = curr[1];
82
83                for (int[] dir : dirs) {
84                    int newRow = row + dir[0];
85                    int newCol = col + dir[1];
86
87                    if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n &&
88                        rooms[newRow][newCol] == 2147483647) {
89                        rooms[newRow][newCol] = distance;
90                        queue.offer(new int[]{newRow, newCol});
91                    }
92                }
93            }
94        }
95    }
96}
97