NUHMAN.com

Introduction

LeetCode 286: Walls and Gates is a problem where you are given a 2D grid representing rooms, walls, and gates. The grid has the following integer values:

• 0: A gate
• -1: A wall
• INF (2147483647): An empty room

The goal is to fill each empty room with the distance to the nearest gate. If a room cannot reach any gate, leave it as INF.

This problem is an example of multi-source BFS (Breadth-First Search), where you start from all gates simultaneously to find the shortest path to each room.

Problem Statement

You are given an m x n 2D grid initialized with the following values:

• 0 represents a gate.
• -1 represents a wall.
• 2147483647 represents an empty room.

You need to fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, the room should remain INF (2147483647).

Example

python

Input: 
[ [INF, -1, 0, INF],
  [INF, INF, INF, -1],
  [INF, -1, INF, -1],
  [0, -1, INF, INF] ]

Output:
[ [3, -1, 0, 1],
  [2, 2, 1, -1],
  [1, -1, 2, -1],
  [0, -1, 3, 4] ]

✅ Step-by-Step Solution

🧠 Intuition

This problem is best solved using Breadth-First Search (BFS):

• BFS is ideal here because it finds the shortest path in an unweighted grid, and we need to fill each room with the shortest distance to a gate.
• Multi-source BFS starts from all gates simultaneously, exploring all possible paths.

Steps:

1. Initialize the grid: Start with a grid that has gates (0), walls (-1), and empty rooms (INF).
2. Multi-source BFS:

• All gates (0) are initial sources.
• Use a queue to perform BFS and propagate the shortest distance to neighboring rooms.

1. BFS traversal: For each room, check its neighbors (up, down, left, right). If a neighboring room is an empty room (INF), update its distance and add it to the queue.
2. Stop when all rooms are filled: Rooms are filled in order of increasing distance from a gate.

✅ Python Code

python

from collections import deque

class Solution:
    def wallsAndGates(self, rooms: list[list[int]]) -> None:
        if not rooms:
            return
        
        # Directions: Up, Down, Left, Right
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        # Initialize a queue for BFS
        queue = deque()
        
        # Add all gates (0s) to the queue as starting points
        for i in range(len(rooms)):
            for j in range(len(rooms[0])):
                if rooms[i][j] == 0:  # It's a gate
                    queue.append((i, j))
        
        # Perform BFS
        while queue:
            x, y = queue.popleft()
            # Check all four possible directions
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                # Ensure we are within bounds and it's an empty room
                if 0 <= nx < len(rooms) and 0 <= ny < len(rooms[0]) and rooms[nx][ny] == 2147483647:
                    rooms[nx][ny] = rooms[x][y] + 1  # Update the distance
                    queue.append((nx, ny))  # Add the neighbor to the queue

🧪 How It Works

1. Initialization:

• Find all gates (0) in the grid and add their positions to the queue.

1. BFS:

• For each gate, explore all adjacent rooms (up, down, left, right).
• If the room is empty (INF), update its distance to be the current gate's distance + 1.
• Add the room to the queue for further exploration.

1. End Condition: The queue will be empty once all reachable rooms have been updated with their shortest distance to the nearest gate.

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(m * n), where m is the number of rows and n is the number of columnsSpace ComplexityO(m * n), for the queue storing grid cells

• The BFS traverses each cell at most once, so time complexity is proportional to the grid size.
• We use a queue to store up to all grid cells in the worst case, hence the space complexity is also O(m * n).

🔍 Edge Cases

1. Empty grid: If the grid is empty, the function should return immediately.
2. No gates: If there are no gates, no room can be updated, so the grid remains unchanged.
3. Walls blocking all paths: If walls block all paths, rooms will remain at INF.

✅ Conclusion

LeetCode 286: Walls and Gates is an excellent problem to practice multi-source BFS. It tests your ability to:

• Perform breadth-first search from multiple starting points.
• Update the grid with the shortest distances in an efficient manner.

This problem can be generalized to other pathfinding scenarios where you need to propagate distances or values across a grid.