30% off Lifetime Premium Access expires December 2nd!

30% off Lifetime Premium Access expires Dec 2nd!

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Get Premium

Leetcode 286. Walls and Gates

Given a 2D grid of empty rooms (INF), walls (-1), and gates (0), fill each empty room with the distance to its nearest gate (leave walls and gates unchanged). This is a multi-source shortest-path problem on a grid that is typically solved by running a BFS from all gates simultaneously to compute minimum distances in O(mn) time.

Asked at:

Doordash

Spotify

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 → a wall or obstacle that cannot be passed through
0 → a gate
2147483647 (which is 2^31 - 1, also referred to as INF) → an empty room

You are tasked to fill each empty room with its shortest distance to the nearest gate.

Distance is measured as the minimum number of steps needed to reach a gate.
Movement is only allowed horizontally or vertically (not diagonally).
If an empty room cannot reach any gate (blocked by walls), it should remain INF.

Input:


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

Explanation: Each empty room is filled with its shortest distance to the nearest gate.

Constraints:

m == rooms.length
n == rooms[i].length
1 <= m, n <= 250
rooms[i][j] is -1, 0, or 2^31 - 1

Note: The algorithm modifies the input grid in-place

Movement is only allowed horizontally or vertically

Unreachable rooms remain as INF

Understanding the Problem

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.

Brute Force Approach

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

Brute force approach: For each empty room, perform BFS to find nearest gate

0 / 181

Test Your Knowledge

Complexity Analysis

Time Complexity: O(k*m*n) where k is the number of empty rooms Due to checking all possible combinations

Space Complexity: O(m*n) for the BFS queue in each iteration Additional space for tracking

Building Intuition

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.

Common Mistakes

Trying to run BFS from each empty room separately, leading to O(kmn) complexity

Forgetting to check bounds when exploring neighbors in the grid

Not handling the case where rooms remain unreachable (should stay as INF)

Using DFS instead of BFS, which doesn't guarantee shortest paths

Modifying cells that are walls or already processed gates

Optimal Solution

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: Start from all gates simultaneously to find shortest distances

0 / 79

Test Your Knowledge

Complexity Analysis

Time Complexity: O(m*n) Single pass through the data

Space Complexity: O(m*n) for the BFS queue Space for the data structure

What We've Learned

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.

Test Your Understanding

Why is matrix the right data structure for this problem?

matrix provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Late October, 2025

Doordash

Senior

Mid September, 2025

Doordash

Staff

Variation of Leet code walls and gates with some walls also been able to have the distance marked

Early August, 2025

Doordash

Mid-level

Get Premium to View All 9 Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 286. Walls and Gates

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact