Walls and Gates

Medium

💭 Introduction

You’re given an m x n grid representing rooms in a building. Each cell can be:

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

Your task: Fill each empty room with the distance to its nearest gate. If it’s impossible to reach a gate, leave it as INF.

This is a classic multi-source BFS problem where we need to find the shortest distance from multiple starting points (gates) simultaneously.

🧩 Problem Statement

LeetCode #286 — Walls and Gates

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

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

Explanation:

Starting from gates (cells with 0):

Top gate at (0,2) fills nearby rooms
Bottom gate at (3,0) fills nearby rooms
Each room gets the minimum distance to any gate

🔍 Example 2:

Input:
-1

Output:
-1

Explanation:

Only a wall, no rooms or gates.

🔍 Example 3:

Input:
INF

Output:
INF

Explanation:

Only an empty room with no gates, so it remains INF.

🧠 Step 1: Understanding the Problem

Let’s break down what we’re really asking:

Key Observations:

Multiple sources: We have multiple gates (starting points)
Shortest distance: We need the minimum distance to ANY gate
4-directional movement: Can move up, down, left, right
Obstacles: Walls (-1) block movement
In-place modification: Update the grid directly

Why BFS?

BFS finds shortest paths in unweighted graphs
Level-by-level exploration ensures we find minimum distances
Multi-source BFS processes all gates simultaneously

Transform the problem:

"Distance to nearest gate"
        ↓
"Multi-source shortest path in a grid"

🤔 Step 2: The Naive Approach (DFS from Each Room)

We could try DFS from each empty room to find the nearest gate:

def wallsAndGates(rooms):
    if not rooms:
        return
    
    m, n = len(rooms), len(rooms[0])
    INF = 2147483647
    
    def dfs(row, col, distance):
        # Out of bounds or wall or already has shorter distance
        if (row < 0 or row >= m or col < 0 or col >= n or
            rooms[row][col] < distance):
            return
        
        rooms[row][col] = distance
        
        # Explore 4 directions
        dfs(row + 1, col, distance + 1)
        dfs(row - 1, col, distance + 1)
        dfs(row, col + 1, distance + 1)
        dfs(row, col - 1, distance + 1)
    
    # Start DFS from each gate
    for i in range(m):
        for j in range(n):
            if rooms[i][j] == 0:
                dfs(i, j, 0)

Problem: DFS doesn’t guarantee shortest path! It might find a longer path first.

⏱️ Time Complexity: $O(m \times n \times m \times n)$ - Very inefficient!

🚀 Step 3: Multi-Source BFS Solution (Optimal)

The key insight: Start BFS from all gates simultaneously!

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 or not rooms[0]:
            return
        
        m, n = len(rooms), len(rooms[0])
        INF = 2147483647
        
        # Find all gates and add to queue
        queue = deque()
        for i in range(m):
            for j in range(n):
                if rooms[i][j] == 0:
                    queue.append((i, j))
        
        # Directions: up, down, left, right
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        
        # BFS from all gates simultaneously
        while queue:
            row, col = queue.popleft()
            
            # Explore all 4 directions
            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
                    rooms[new_row][new_col] = rooms[row][col] + 1
                    queue.append((new_row, new_col))

⏱️ Time Complexity: $O(m \times n)$ - Visit each cell at most once

📦 Space Complexity: $O(m \times n)$ - Queue can hold all cells in worst case

⚙️ Step 4: Step-by-Step Trace

Let’s trace through Example 1:

Initial Grid:

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

Step-by-step BFS:

Level	Queue	Action	Grid State
0	[(0,2), (3,0)]	Start with gates	Same as initial
1	[(0,3), (1,2), (2,0)]	Process (0,2) and (3,0)	Update neighbors to 1
2	[(1,1), (1,3), (2,2)]	Process level 1 cells	Update neighbors to 2
3	[(0,0), (2,4)]	Process level 2 cells	Update neighbors to 3
4	[(3,4)]	Process level 3 cells	Update neighbors to 4
5	[]	Done	Final state

Final Grid:

🎯 Step 5: Alternative Implementation (Cleaner)

Using a helper function for cleaner code:

from collections import deque

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        if not rooms or not rooms[0]:
            return
        
        m, n = len(rooms), len(rooms[0])
        INF = 2147483647
        
        def is_valid(row, col):
            """Check if cell is within bounds and is an empty room"""
            return (0 <= row < m and 0 <= col < n and 
                    rooms[row][col] == INF)
        
        # Initialize queue with all gates
        queue = deque()
        for i in range(m):
            for j in range(n):
                if rooms[i][j] == 0:
                    queue.append((i, j))
        
        # BFS
        while queue:
            row, col = queue.popleft()
            current_distance = rooms[row][col]
            
            # Check all 4 neighbors
            for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                new_row, new_col = row + dr, col + dc
                
                if is_valid(new_row, new_col):
                    rooms[new_row][new_col] = current_distance + 1
                    queue.append((new_row, new_col))

🧮 Step 6: With Distance Tracking

If you need to track distances separately:

from collections import deque

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        if not rooms or not rooms[0]:
            return
        
        m, n = len(rooms), len(rooms[0])
        INF = 2147483647
        
        # Find all gates
        queue = deque()
        for i in range(m):
            for j in range(n):
                if rooms[i][j] == 0:
                    queue.append((i, j, 0))  # (row, col, distance)
        
        # BFS with explicit distance tracking
        while queue:
            row, col, dist = queue.popleft()
            
            for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                new_row, new_col = row + dr, col + dc
                
                if (0 <= new_row < m and 0 <= new_col < n and
                    rooms[new_row][new_col] == INF):
                    
                    rooms[new_row][new_col] = dist + 1
                    queue.append((new_row, new_col, dist + 1))

🎯 Key Insights

Multi-source BFS: Start from all gates simultaneously, not one at a time
Level-by-level: BFS naturally processes cells by distance level
First visit is shortest: Once a cell is visited, it has the shortest distance
In-place modification: Update the grid directly, no need for separate distance array
Early termination: Only process INF cells (unvisited rooms)

📊 Complexity Summary

Approach	Time	Space	Notes
DFS from each room	$O((mn)^2)$	$O(mn)$	Inefficient, doesn’t guarantee shortest
BFS from each gate separately	$O(k \times mn)$	$O(mn)$	k = number of gates
Multi-source BFS	$O(mn)$	$O(mn)$	Optimal solution

Where m = number of rows, n = number of columns

🌟 Edge Cases to Consider

Empty grid: rooms = [] → Return immediately
No gates: All cells remain INF
No empty rooms: Only gates and walls
Single cell: Could be gate, wall, or empty room
All walls: Grid of -1s
Disconnected regions: Some rooms unreachable from any gate

💡 Common Mistakes

Starting BFS from rooms instead of gates: Wrong approach, doesn’t work
Using DFS: Doesn’t guarantee shortest path
Processing gates one at a time: Inefficient, doesn’t give correct distances
Not checking if cell is INF: Might overwrite shorter distances
Wrong boundary checks: Index out of bounds errors

🧪 Test Cases

# Test Case 1: Standard grid
rooms = [
    [2147483647, -1, 0, 2147483647],
    [2147483647, 2147483647, 2147483647, -1],
    [2147483647, -1, 2147483647, -1],
    [0, -1, 2147483647, 2147483647]
]
# Expected: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

# Test Case 2: No gates
rooms = [[2147483647, 2147483647], [2147483647, 2147483647]]
# Expected: [[2147483647, 2147483647], [2147483647, 2147483647]]

# Test Case 3: All gates
rooms = [[0, 0], [0, 0]]
# Expected: [[0, 0], [0, 0]]

# Test Case 4: Disconnected regions
rooms = [
    [2147483647, -1, 0],
    [-1, -1, -1],
    [0, -1, 2147483647]
]
# Expected: [[1,-1,0],[-1,-1,-1],[0,-1,2147483647]]

# Test Case 5: Single gate
rooms = [[0]]
# Expected: [[0]]

🔍 Variations of This Problem

01 Matrix (LC 542) - Similar but find distance to nearest 0
Rotting Oranges (LC 994) - Multi-source BFS with time tracking
Shortest Path in Binary Matrix (LC 1091) - BFS with obstacles
As Far from Land as Possible (LC 1162) - Find maximum distance

Network Delay Time - Single-source shortest path
Dijkstra’s Algorithm - Weighted shortest path
Number of Islands - Grid traversal with DFS/BFS
Surrounded Regions - Grid boundary problem

🏆 Why This Problem Matters

Multi-source BFS: Fundamental technique for many problems
Grid traversal: Common pattern in interviews
Shortest path: Core graph algorithm concept
Real-world applications: Navigation, facility location, network design
Interview favorite: Tests BFS understanding and optimization

🎓 Key Takeaways

Multi-source BFS: Start from all sources simultaneously
Level-by-level processing: BFS naturally finds shortest distances
In-place modification: Efficient space usage
First visit wins: Once visited, distance is optimal
Grid as graph: Treat 2D grid as implicit graph

📝 Interview Tips

Clarify constraints: Confirm grid dimensions, value ranges
Explain multi-source BFS: Show you understand the key insight
Handle edge cases: Empty grid, no gates, all walls
Optimize space: Discuss in-place modification
Test thoroughly: Walk through a small example
Discuss complexity: Explain why O(mn) is optimal

🔧 Python Tips

# Using deque for efficient queue operations
from collections import deque
queue = deque()

# Direction vectors for cleaner code
directions = [(1,0), (-1,0), (0,1), (0,-1)]

# Boundary check helper
def is_valid(row, col, m, n):
    return 0 <= row < m and 0 <= col < n

# INF constant
INF = 2147483647  # or float('inf')

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

🎯 Problem-Solving Pattern

This problem follows the Multi-Source BFS pattern:

Identify: Need shortest distance from multiple sources
Initialize: Add all sources to queue at once
Process: BFS level by level
Update: Mark visited cells with their distance
Terminate: When queue is empty

This pattern applies to many similar grid/graph problems!

🌟 Optimization Notes

Why multi-source BFS is optimal:

Processes all gates simultaneously
Each cell visited exactly once
No redundant distance calculations
Natural level-by-level expansion ensures shortest paths

Space optimization:

In-place modification saves O(mn) space
Queue size is at most O(mn) in worst case
No need for separate visited array (use INF check)

Walls and Gates

💭 Introduction

🔍 Example 1:

🔍 Example 2:

🔍 Example 3:

🧠 Step 1: Understanding the Problem

🤔 Step 2: The Naive Approach (DFS from Each Room)

🚀 Step 3: Multi-Source BFS Solution (Optimal)

⚙️ Step 4: Step-by-Step Trace

🎯 Step 5: Alternative Implementation (Cleaner)

🧮 Step 6: With Distance Tracking

🎯 Key Insights

📊 Complexity Summary

🌟 Edge Cases to Consider

💡 Common Mistakes

🧪 Test Cases

🔍 Variations of This Problem

💡 Related Problems

🏆 Why This Problem Matters

🎓 Key Takeaways

📝 Interview Tips

🔧 Python Tips

🎯 Problem-Solving Pattern

🌟 Optimization Notes