[DSA][Graph] Walls and Gates

Leetcode 286

You are given an m × 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 2³¹ — 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.

**[What can I ask?]

• **Can the rooms grid be empty? YES

**[Key Idea]

• Perform multi-source BFS** from all gates, updating the distance of each reachable empty room (INF) to the nearest gate.

[Solution 1] Breadth First Search

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        if not rooms:
            return

        INF = 2147483647
        ROW, COL = len(rooms), len(rooms[0])
        directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]

        q = deque()

        for i in range(ROW):
            for j in range(COL):
                if rooms[i][j] == 0:
                    q.append((i, j))

        while q:
            x, y = q.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < ROW and 0 <= ny < COL and rooms[nx][ny] == INF:
                    rooms[nx][ny] = rooms[x][y] + 1
                    q.append((nx, ny))

This problem is about finding the shortest distance from each empty room (INF) to the nearest gate (0). To solve it efficiently, we can use a multi-source BFS approach.

Multi-source BFS means running BFS starting from multiple sources at the same time.

• First, add all gates (0) into a queue.
• Then, repeatedly dequeue a position and explore its up, down, left, and right neighbors.
• If a neighbor is an empty room (INF), update its distance to current distance + 1 and enqueue it.
• This way, all gates simultaneously propagate their distances, allowing us to efficiently fill in the shortest distances.

While we could also use DFS starting from each gate to recursively update distances, DFS does not guarantee shortest paths because it explores deeply first.

• Some rooms may be revisited multiple times, leading to unnecessary computations and potential stack overflow.
• In contrast, BFS ensures that the first time a room is visited, it is the shortest distance, so no additional calculations or comparisons are needed.

⏱️ Time Complexity Each cell is visited at most once during the BFS. Therefore, the overall time complexity is O(m × n), where m and n are the grid dimensions.

🧠 Space Complexity We do not use an extra visited array; instead, we update the input grid in place. Therefore, the additional space complexity is O(1).