Problem Description

You have a grid representing a floor plan with rooms, walls, and gates. The grid is an m x n matrix where each cell contains one of three values:

• -1 represents a wall or obstacle that cannot be passed through
• 0 represents a gate
• 2147483647 (which is 2^31 - 1, also referred to as INF) represents an empty room

Your task is to fill each empty room with its shortest distance to the nearest gate. The distance is measured as the minimum number of steps needed to reach a gate from that room, moving only horizontally or vertically (not diagonally).

If an empty room cannot reach any gate because it's blocked by walls, it should remain as INF.

The solution uses a multi-source BFS approach. It starts from all gates simultaneously (distance 0) and spreads outward level by level. First, all gate positions are added to a queue. Then, the algorithm processes each level of distance incrementally - all rooms at distance 1 from gates are filled with 1, then all rooms at distance 2 are filled with 2, and so on.

The key insight is that by starting from all gates at once and expanding outward, each empty room will be reached first by its nearest gate, automatically giving us the shortest distance. Once a room is visited and assigned a distance value, it won't be visited again, ensuring optimal distances are preserved.

The algorithm modifies the input grid in-place, replacing each INF value with the actual distance to the nearest gate, while keeping walls as -1 and gates as 0.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The grid can be viewed as a graph where each cell is a node, and adjacent cells (up, down, left, right) are connected by edges. We need to traverse this graph to find distances.

Is it a tree?

• No: The grid structure is not a tree - it can have multiple paths between nodes and cycles (you can move in a square and return to the starting position).

Is the problem related to directed acyclic graphs?

• No: The grid allows bidirectional movement between adjacent cells, and cycles are possible.

Is the problem related to shortest paths?

• Yes: We need to find the shortest distance from each empty room to its nearest gate, which is a classic shortest path problem.

Is the graph Weighted?

• No: Each step from one cell to an adjacent cell has the same cost (distance of 1). All edges have uniform weight.

BFS

• Yes: Since we have an unweighted graph and need to find shortest paths, BFS is the appropriate algorithm.

Conclusion: The flowchart correctly leads us to use BFS (Breadth-First Search) for this problem. BFS is ideal here because:

1. We're working with an unweighted graph (each step has equal cost)
2. We need to find shortest distances
3. We can leverage multi-source BFS by starting from all gates simultaneously, which efficiently computes the minimum distance to any gate for each room

Intuition

The key insight comes from thinking about how water would naturally flow from multiple sources. Imagine each gate as a water source that spreads outward simultaneously. The water from each gate expands one step at a time in all four directions. When water from a gate reaches an empty room, that room gets "colored" with the distance traveled. The crucial point is that whichever gate's "water" reaches a room first must be the closest gate to that room.

This naturally leads us to a multi-source BFS approach. Instead of running BFS from each empty room to find its nearest gate (which would be inefficient), we flip the problem: we start from all gates at once and expand outward.

Why does this work? Consider what happens at each distance level:

• At distance 0: All gates are in the queue
• At distance 1: All rooms exactly 1 step away from any gate get marked with distance 1
• At distance 2: All unmarked rooms exactly 2 steps away from the nearest gate get marked with distance 2

The beauty of BFS is that it explores nodes level by level. When we process all nodes at distance d before moving to distance d+1, we guarantee that each room is reached via the shortest path. Once a room is marked with a distance, we never visit it again - this ensures it keeps its shortest distance value.

This approach is efficient because:

1. Each room is visited at most once (O(mn) time complexity)
2. We don't need to run separate BFS from each room or gate
3. The simultaneous expansion from all gates naturally gives us the minimum distances

The algorithm essentially creates expanding "waves" from each gate, and wherever these waves first meet an empty room, that's the shortest distance from that room to any gate.

Solution Approach

The implementation follows a standard multi-source BFS pattern with these key components:

1. Initial Setup:

• Extract grid dimensions: m (rows) and n (columns)
• Define inf = 2**31 - 1 as the value representing empty rooms
• Create a queue and initialize it with all gate positions: [(i, j) for i in range(m) for j in range(n) if rooms[i][j] == 0]
• Initialize distance counter d = 0

2. Queue Initialization: The queue starts with all gates (cells with value 0). This is the multi-source aspect - instead of one starting point, we have multiple starting points expanding simultaneously.

3. Level-by-Level BFS Processing:

while q:
    d += 1  # Increment distance for the next level
    for _ in range(len(q)):  # Process all nodes at current distance level

The outer while loop continues as long as there are cells to process. The d += 1 increments the distance for each new level. The inner for loop with range(len(q)) ensures we process exactly the nodes that were in the queue at the start of this distance level - this maintains the level-by-level traversal.

4. Exploring Neighbors:

i, j = q.popleft()
for a, b in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
    x, y = i + a, j + b

For each cell, we check all four directions (right, left, down, up) by using direction vectors [[0, 1], [0, -1], [1, 0], [-1, 0]].

5. Updating Empty Rooms:

if 0 <= x < m and 0 <= y < n and rooms[x][y] == inf:
    rooms[x][y] = d
    q.append((x, y))

For each neighbor, we check:

• Is it within grid boundaries? (0 <= x < m and 0 <= y < n)
• Is it an unvisited empty room? (rooms[x][y] == inf)

If both conditions are met, we:

• Update the room with the current distance d
• Add this newly updated room to the queue so it can spread the distance to its neighbors in the next level

Why This Works:

• Rooms with value -1 (walls) are never added to the queue
• Rooms with value 0 (gates) are never updated since we only update rooms with value inf
• Each empty room is updated exactly once with its shortest distance
• The in-place modification means no extra space is needed beyond the queue

The algorithm terminates when the queue is empty, meaning all reachable empty rooms have been assigned their shortest distances to a gate. Any rooms still containing inf are unreachable from any gate.

Example Walkthrough

Let's walk through a small example to illustrate the multi-source BFS approach.

Initial Grid:

INF  -1   0  INF
INF  INF INF  -1
INF  -1  INF  -1
 0   -1  INF INF

Where INF = 2147483647 represents empty rooms, -1 represents walls, and 0 represents gates.

Step 1: Initialize Queue with All Gates

• Find all gates: positions (0,2) and (3,0)
• Queue: [(0,2), (3,0)]
• Distance d = 0

Step 2: Process Distance Level 1

• Increment d = 1
• Process gate at (0,2):
  • Check neighbors: up (out of bounds), down (1,2), left (0,1), right (0,3)
  • (1,2) is INF → update to 1, add to queue
  • (0,1) is -1 (wall) → skip
  • (0,3) is INF → update to 1, add to queue
• Process gate at (3,0):
  • Check neighbors: up (2,0), down (out of bounds), left (out of bounds), right (3,1)
  • (2,0) is INF → update to 1, add to queue
  • (3,1) is -1 (wall) → skip
• Queue after level 1: [(1,2), (0,3), (2,0)]

Grid after distance 1:

  1  -1   0   1
INF   1   1  -1
  1  -1  INF -1
  0  -1  INF INF

Step 3: Process Distance Level 2

• Increment d = 2
• Process (1,2):
  • Neighbors: (1,1) is INF → update to 2, add to queue
  • Others are walls, already visited, or out of bounds
• Process (0,3):
  • All neighbors are walls, already visited, or out of bounds
• Process (2,0):
  • Neighbors: (1,0) is INF → update to 2, add to queue
  • Others are walls, already visited, or out of bounds
• Queue after level 2: [(1,1), (1,0)]

Grid after distance 2:

  1  -1   0   1
  2   2   1  -1
  1  -1  INF -1
  0  -1  INF INF

Step 4: Process Distance Level 3

• Increment d = 3
• Process (1,1):
  • Neighbors: (0,0) is INF → update to 3, add to queue
  • Others are already visited or walls
• Process (1,0):
  • All neighbors are already visited or walls
• Queue after level 3: [(0,0)]

Grid after distance 3:

  3  -1   0   1
  2   2   1  -1
  1  -1  INF -1
  0  -1  INF INF

Step 5: Process Distance Level 4

• Increment d = 4
• Process (0,0):
  • All neighbors are walls or already visited
• Queue becomes empty

Final Grid:

  3  -1   0   1
  2   2   1  -1
  1  -1  INF -1
  0  -1  INF INF

The rooms at positions (2,2), (3,2), and (3,3) remain as INF because they are unreachable from any gate due to being blocked by walls. Each other empty room now contains its shortest distance to the nearest gate.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the grid.

• The initial scan to find all gates (value 0) takes O(m * n) time as we iterate through the entire grid once.
• In the BFS traversal, each cell is visited at most once. When a cell is updated from INF to a distance value, it's added to the queue exactly once and processed exactly once.
• The four directional checks for each cell are constant time operations O(4) = O(1).
• Therefore, the total time complexity is O(m * n) for the initial scan plus O(m * n) for processing all cells, resulting in O(m * n) overall.

Space Complexity: O(m * n) in the worst case.

• The queue q can contain at most O(m * n) elements. This occurs when all cells are gates (value 0) initially, causing all cells to be in the queue at the start.
• In a more typical scenario where gates are limited, the queue size would be proportional to the number of cells at the current "frontier" of the BFS, which could still be O(min(m, n)) in cases like when gates are along one edge.
• The algorithm modifies the input array in-place, so no additional space is used for storing the result.
• Therefore, the space complexity is O(m * n) in the worst case due to the queue storage.

Common Pitfalls

1. Incorrect Distance Tracking - Updating Distance at Wrong Time

A common mistake is incrementing the distance counter at the wrong point in the BFS traversal, leading to incorrect distance values for rooms.

Incorrect Implementation:

distance = 0
while queue:
    for _ in range(len(queue)):
        current_row, current_col = queue.popleft()
        distance += 1  # Wrong! Distance incremented for each cell
      
        for row_offset, col_offset in directions:
            next_row = current_row + row_offset
            next_col = current_col + col_offset
            if (0 <= next_row < rows and 
                0 <= next_col < cols and 
                rooms[next_row][next_col] == INF):
                rooms[next_row][next_col] = distance
                queue.append((next_row, next_col))

Why it's wrong: This increments distance for every cell processed, not for every level of BFS. Cells at the same distance from gates would get different distance values.

Correct Approach: Increment distance once per level, before processing all cells at that level:

distance = 0
while queue:
    distance += 1  # Increment once for the entire level
    level_size = len(queue)
    for _ in range(level_size):
        current_row, current_col = queue.popleft()
        # Process neighbors...

2. Processing Wrong Number of Cells Per Level

Another pitfall is not properly maintaining level-by-level traversal by failing to capture the queue size at the start of each level.

Incorrect Implementation:

while queue:
    distance += 1
    for _ in range(len(queue)):  # Bug: len(queue) changes during iteration!
        current_row, current_col = queue.popleft()
        for row_offset, col_offset in directions:
            # ... adding new cells to queue changes its length
            queue.append((next_row, next_col))

Why it's wrong: When written inline like for _ in range(len(queue)), if the queue implementation allows dynamic length checking, you might process newly added cells in the same level, breaking the level-order traversal.

Correct Approach: Store the level size before the loop:

level_size = len(queue)  # Capture size before processing
for _ in range(level_size):
    # Now we process exactly 'level_size' cells

3. Starting Distance at Wrong Value

Incorrect Implementation:

distance = 1  # Wrong starting value!
while queue:
    # Process cells...
    rooms[next_row][next_col] = distance
    distance += 1

Why it's wrong: Gates are at distance 0. The first empty rooms adjacent to gates should be at distance 1. Starting with distance = 1 and incrementing after assignment would give wrong distances.

Correct Approach: Either:

• Start with distance = 0 and increment at the beginning of each level (as shown in the solution)
• Or start with distance = 1 but increment at the end of processing each level

4. Not Handling Edge Cases Properly

Potential Issues:

• Empty grid or grid with no gates
• Grid with only walls and gates (no empty rooms)
• Single cell grid

Solution: The current implementation handles these gracefully:

• If no gates exist, the queue starts empty and the while loop never executes
• If no empty rooms exist, neighbors are never updated (the condition rooms[x][y] == INF fails)
• Single cell grids work correctly as the loops handle m=1, n=1 appropriately