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

Additional information

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

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 = [[-1]]

Output: [[-1]]

Brute Force (DFS from Every Gate)

Intuition

A straightforward way to solve this is to find every single gate (0) in the grid. Whenever we find a gate, we can start a Depth-First Search (DFS) that walks through the empty rooms. As we walk, we pass down the current distance from the gate.

If we step into an empty room, we update its value to the current distance. If that room already has a distance value (because another gate reached it first), we only overwrite it and continue our DFS if our new distance is strictly smaller than its current value.

Algorithm

1. Store the dimensions rows and cols of the grid.
2. Create a recursive helper function dfs(r, c, current_dist).

• Base Cases: If r or c are out of bounds, return immediately.
• Pruning: If rooms[r][c] < current_dist, it means this cell is either a wall (-1), a gate (0), or an empty room that has already been reached by a shorter or equal path. Return immediately to prune the search!
• Update: Set rooms[r][c] = current_dist.
• Recurse: Call dfs on the 4 adjacent neighbors, passing current_dist + 1.

3. Loop through every row and column in the grid.
4. If rooms[r][c] == 0, call dfs(r, c, 0).
5. The grid is modified in-place, so no explicit return is required.

def walls_and_gates(rooms: list[list[int]]) -> list[list[int]]:
    if not rooms or not rooms[0]:
        return
        
    rows, cols = len(rooms), len(rooms[0])
    
    def dfs(r, c, current_dist):
        if (r < 0 or r >= rows or c < 0 or c >= cols or 
            rooms[r][c] < current_dist):
            return
            
        rooms[r][c] = current_dist
        
        dfs(r + 1, c, current_dist + 1)
        dfs(r - 1, c, current_dist + 1)
        dfs(r, c + 1, current_dist + 1)
        dfs(r, c - 1, current_dist + 1)
        
    for r in range(rows):
        for c in range(cols):
            if rooms[r][c] == 0:
                dfs(r, c, 0)

Time & Space Complexity

• Time complexity: O((M * N)^2)

• Reason: In the worst-case scenario, the grid is entirely empty rooms with multiple gates. Each gate triggers a DFS that can potentially visit every cell in the M * N grid.

• Space complexity: O(M * N)

• Reason: The recursion stack for the DFS can grow as deep as the total number of cells in the grid.

Multi-Source Breadth-First Search (BFS) - Optimal

Intuition

Instead of updating the distances one gate at a time, what if all gates expanded outward simultaneously?

This is the perfect use case for a Multi-Source BFS. We scan the grid once to find every single gate, and put all their coordinates into a Queue. Then, we process the queue level by level. Because BFS guarantees the shortest path in an unweighted grid, the very first time an empty room is reached by the spreading BFS, we are mathematically guaranteed that it is the absolute shortest distance to any gate!

We instantly update the room's distance and add it to the queue to continue the outward spread.

Algorithm

1. If the grid is empty, return immediately.
2. Store rows, cols, and define INF = 2147483647.
3. Initialize a deque (queue).
4. Initial Scan: Loop through every cell in the grid. If rooms[r][c] == 0, add its coordinates (r, c) to the queue.
5. Multi-Source BFS: While the queue is not empty:

• Pop the front coordinates row, col.
• Check the 4 adjacent neighbors (up, down, left, right).
• If a neighbor is within bounds and its value is exactly INF (meaning it's an unvisited empty room):
• Update its distance: rooms[nr][nc] = rooms[row][col] + 1.
• Add the neighbor to the queue so it can spread its distance outward on the next level.

def walls_and_gates(rooms: list[list[int]]) -> list[list[int]]:
    if not rooms or not rooms[0]:
        return
        
    rows, cols = len(rooms), len(rooms[0])
    q = deque()
    INF = 2147483647
    
    # Put all gates into the queue simultaneously
    for r in range(rows):
        for c in range(cols):
            if rooms[r][c] == 0:
                q.append((r, c))
                
    directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    
    while q:
        r, c = q.popleft()
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            
            # If the neighbor is an empty, unvisited room
            if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == INF:
                rooms[nr][nc] = rooms[r][c] + 1
                q.append((nr, nc))

Time & Space Complexity

• Time complexity: O(M * N)

• Reason: We iterate over the grid once to find the gates. During the BFS, every empty room is added to the queue exactly once and processed. The total operations scale perfectly linearly with the number of cells.

• Space complexity: O(M * N)

• Reason: In the worst-case scenario (where almost the entire grid is made of gates), the queue will hold O(M * N) coordinates at the start.
  return rooms