Leetcode 286. Walls and Gates

This problem is asking us to find the shortest path from every empty room to its nearest gate in a 2D grid. We need to handle three types of cells: walls (-1) that block movement, gates (0) that are our destinations, and empty rooms (INF) that need to be filled with their distance to the nearest gate.

The key constraint is that we can only move horizontally or vertically, which means we're working with Manhattan distance. Each step from one cell to an adjacent cell costs exactly 1 unit of distance.

We need to handle the case where some rooms might be completely unreachable due to walls blocking all paths to gates - these should remain as INF.

The most straightforward approach would be to iterate through each empty room (INF cell) and perform a separate BFS from that room to find the nearest gate. For each empty room, we would start a BFS traversal, exploring all four directions level by level until we encounter a gate (value 0).

This means for every empty room, we're doing a complete BFS search that could potentially visit the entire grid. If we have k empty rooms, we're performing k separate BFS operations, each potentially taking O(m*n) time in the worst case.

The major inefficiency here is the redundant work - we're exploring the same paths multiple times from different starting points, and we're not leveraging the fact that BFS naturally finds shortest paths.

def wallsAndGates(rooms):
    if not rooms or not rooms[0]:
        return
    
    m, n = len(rooms), len(rooms[0])
    INF = 2147483647
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    # Find all empty rooms and perform BFS from each
    for i in range(m):
        for j in range(n):
            if rooms[i][j] == INF:
                # BFS from this empty room to find nearest gate
                queue = [(i, j)]
                visited = set()
                visited.add((i, j))
                distance = 0
                found_gate = False
                
                while queue and not found_gate:
                    next_queue = []
                    for row, col in queue:
                        if rooms[row][col] == 0:
                            rooms[i][j] = distance
                            found_gate = True
                            break
                        
                        # Explore all four directions
                        for dr, dc in directions:
                            new_row, new_col = row + dr, col + dc
                            if (0 <= new_row < m and 0 <= new_col < n and 
                                (new_row, new_col) not in visited and 
                                rooms[new_row][new_col] != -1):
                                visited.add((new_row, new_col))
                                next_queue.append((new_row, new_col))
                    
                    queue = next_queue
                    distance += 1

The breakthrough insight is recognizing this as a multi-source shortest path problem rather than multiple single-source problems. By starting from all gates simultaneously, we let them 'compete' to reach each empty room, and the first one to arrive is guaranteed to provide the shortest distance.

After seeing the brute force limitations, multi-source BFS is the perfect approach because it leverages the fundamental property that BFS finds shortest paths in unweighted graphs. Instead of running separate BFS from each empty room, we flip the perspective and run a single BFS from all gates simultaneously.

This works because of BFS's level-by-level exploration pattern. When we start from all gates at distance 0, then explore all cells at distance 1, then distance 2, and so on, we guarantee that each empty room is reached by its nearest gate first. The queue naturally maintains the frontier of cells to explore at each distance level.

The grid structure perfectly supports BFS traversal with its four-directional connectivity, and the in-place modification allows us to use the grid itself to track visited cells.

Now that we understand why multi-source BFS is perfect, here's how we implement it. We start by scanning the entire grid to find all gates (cells with value 0) and add their coordinates to a queue. This queue represents our starting frontier.

Next, we perform a single BFS traversal, but instead of starting from one source, we start from all gates simultaneously. In each iteration, we process all cells at the current distance level, then move to the next level. For each cell we process, we check its four neighbors - if a neighbor is an empty room (INF), we update it with the current distance + 1 and add it to the queue for the next level.

The beauty of this approach is that when we first reach any empty room, we're guaranteed to have found the shortest path to it, because BFS explores in order of increasing distance. Once a room is visited and updated, we never need to visit it again.

from collections import deque
def wallsAndGates(rooms):
    if not rooms or not rooms[0]:
        return
    
    m, n = len(rooms), len(rooms[0])
    INF = 2147483647
    queue = deque()
    
    # Find all gates and add them to queue
    for i in range(m):
        for j in range(n):
            if rooms[i][j] == 0:
                queue.append((i, j))
    
    # Directions for 4-directional movement
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    # Multi-source BFS
    while queue:
        row, col = queue.popleft()
        
        # Check all 4 neighbors
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            # Check bounds and if it's an empty room
            if (0 <= new_row < m and 0 <= new_col < n and 
                rooms[new_row][new_col] == INF):
                
                # Update distance and add to queue
                rooms[new_row][new_col] = rooms[row][col] + 1
                queue.append((new_row, new_col))

• Multi-source BFS pattern: When you need shortest distances from multiple starting points simultaneously, initialize your queue with all sources at once rather than running separate BFS from each - this automatically finds the nearest source for each destination in a single traversal.
• In-place grid modification: Use the input grid itself as your visited array by overwriting INF values with actual distances - this eliminates the need for a separate visited matrix and naturally prevents revisiting cells since distance values are always less than INF.
• Level-by-level expansion optimization: BFS guarantees that the first time you reach any cell, you've found the shortest path to it - this property eliminates the need for distance comparison or relaxation steps that other shortest-path algorithms require.
• Boundary validation before queuing: Always check grid boundaries and cell validity (not a wall, still INF) before adding neighbors to the queue, not after popping them - this prevents unnecessary queue operations and potential index errors.
• Grid traversal with direction arrays: Use direction arrays `[(0,1), (1,0), (0,-1), (-1,0)]` for clean 4-directional movement instead of hardcoding four separate boundary checks - this makes the code more maintainable and less error-prone.
• Distance propagation in matrices: This multi-source BFS approach applies to any problem involving spreading influence, infection modeling, or finding nearest facilities in a 2D space - think fire spread, virus transmission, or facility location optimization.