Walls and Gates

Problem

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 means an empty room. We use the value 2^31 - 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.

Example 1:

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

Example 2:

Input: rooms = [[0]]
Output: [[0]]

Constraints:

m == rooms.length
n == rooms[i].length
1 <= m, n <= 250
rooms[i][j] is -1, 0, or 2^31 - 1.

Solution

Approach: Multi-Source BFS from All Gates

The key insight is to start BFS from all gates simultaneously, filling in distances as we explore outward.

Implementation

from collections import deque

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        if not rooms:
            return

        m, n = len(rooms), len(rooms[0])
        INF = 2147483647
        queue = deque()

        # Find all gates and add to queue
        for i in range(m):
            for j in range(n):
                if rooms[i][j] == 0:
                    queue.append((i, j, 0))  # (row, col, distance)

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while queue:
            r, c, dist = queue.popleft()

            for dr, dc in directions:
                nr, nc = r + dr, c + dc

                # Check if neighbor is an empty room (INF)
                if (0 <= nr < m and 0 <= nc < n and
                    rooms[nr][nc] == INF):
                    rooms[nr][nc] = dist + 1
                    queue.append((nr, nc, dist + 1))

Alternative Implementation (Level-by-Level)

from collections import deque

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

        m, n = len(rooms), len(rooms[0])
        INF = 2147483647
        queue = deque()

        # Find all gates
        for i in range(m):
            for j in range(n):
                if rooms[i][j] == 0:
                    queue.append((i, j))

        distance = 0
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while queue:
            distance += 1
            # Process all rooms at current distance
            for _ in range(len(queue)):
                r, c = queue.popleft()

                for dr, dc in directions:
                    nr, nc = r + dr, c + dc

                    if (0 <= nr < m and 0 <= nc < n and
                        rooms[nr][nc] == INF):
                        rooms[nr][nc] = distance
                        queue.append((nr, nc))

Complexity Analysis

Time Complexity: O(m * n), where m and n are grid dimensions. We visit each cell at most once.
Space Complexity: O(m * n) for the queue in worst case.

Key Insights

Multi-Source BFS: Starting from all gates simultaneously ensures we find the shortest distance to any gate for each room.
Natural Distance Calculation: BFS naturally computes shortest paths in unweighted graphs, making it perfect for this problem.
Visit Once: Each room is visited and updated only once, ensuring optimal distances.
In-Place Modification: We modify the input grid directly, using INF as a marker for unvisited rooms.
Impossibility Handling: Rooms that remain INF after BFS are unreachable from any gate.