Walls and Gates - Practice Coding Problems

Walls and Gates - Problem

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. We use the value 2³¹ - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647

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.

Input & Output

Example 1 — Basic Grid with Gates and Walls

$ Input: rooms = [[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]]

💡 Note: Gates at (0,2) and (3,0) spread their distances. Room at (0,0) is 3 steps from nearest gate, room at (0,3) is 1 step from gate at (0,2).

Example 2 — Single Room

$ Input: rooms = [[-1]]

› Output: [[-1]]

💡 Note: Only a wall, no changes needed since there are no gates or empty rooms.

Example 3 — Unreachable Room

$ Input: rooms = [[2147483647,-1],[0,2147483647]]

› Output: [[2147483647,-1],[0,2147483647]]

💡 Note: Gate at (1,0) cannot reach room at (0,0) due to wall at (0,1). Room at (1,1) cannot reach gate either.

Constraints

m == rooms.length
n == rooms[i].length
1 ≤ m, n ≤ 250
rooms[i][j] is -1, 0, or 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Grid with gates (0), walls (-1), and empty rooms (INF)

Distance Propagation

BFS spreads distances from all gates simultaneously

Final Result

Each empty room filled with shortest distance to any gate

Key Takeaway

🎯 Key Insight: Start BFS from all gates at once instead of searching from each room individually

Asked in

G Google 42 f Facebook 38 a Amazon 35 M Microsoft 28

The key insight is to start BFS from all gates simultaneously rather than searching from each empty room. This multi-source BFS approach ensures each cell is visited exactly once, giving us optimal O(mn) time complexity. Best approach is Multi-Source BFS. Time: O(mn), Space: O(mn)

Common Approaches

Approach	Time	Space	Notes
✓ Multi-Source BFS (Optimal)	O(mn)	O(mn)	Start BFS from all gates simultaneously to find shortest distances
Brute Force - DFS from Each Room	O(m²n²)	O(mn)	For each empty room, find shortest path to any gate using DFS

Multi-Source BFS (Optimal) — Algorithm Steps

Find all gates and add to queue with distance 0
Process each level: for each cell, update empty neighbors with distance+1
Continue until queue is empty - all reachable rooms are filled

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Add all gates to queue with distance 0

BFS Expansion

Process level by level, updating empty neighbors

Complete

All reachable rooms filled with shortest distances

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INF 2147483647
#define MAX_QUEUE 10000

typedef struct {
    int row, col, dist;
} QueueItem;

int main() {
    // Simple parsing for small test cases
    int m = 4, n = 4;
    int** rooms = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        rooms[i] = (int*)malloc(n * sizeof(int));
    }
    
    // Example: [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
    rooms[0][0] = INF; rooms[0][1] = -1; rooms[0][2] = 0; rooms[0][3] = INF;
    rooms[1][0] = INF; rooms[1][1] = INF; rooms[1][2] = INF; rooms[1][3] = -1;
    rooms[2][0] = INF; rooms[2][1] = -1; rooms[2][2] = INF; rooms[2][3] = -1;
    rooms[3][0] = 0; rooms[3][1] = -1; rooms[3][2] = INF; rooms[3][3] = INF;
    
    QueueItem queue[MAX_QUEUE];
    int front = 0, rear = 0;
    
    // Add all gates to queue
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (rooms[i][j] == 0) {
                queue[rear++] = (QueueItem){i, j, 0};
            }
        }
    }
    
    int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    while (front < rear) {
        QueueItem curr = queue[front++];
        
        for (int d = 0; d < 4; d++) {
            int newRow = curr.row + directions[d][0];
            int newCol = curr.col + directions[d][1];
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && 
                rooms[newRow][newCol] == INF) {
                rooms[newRow][newCol] = curr.dist + 1;
                queue[rear++] = (QueueItem){newRow, newCol, curr.dist + 1};
            }
        }
    }
    
    // Print result
    printf("[");
    for (int i = 0; i < m; i++) {
        printf("[");
        for (int j = 0; j < n; j++) {
            printf("%d", rooms[i][j]);
            if (j < n - 1) printf(",");
        }
        printf("]");
        if (i < m - 1) printf(",");
    }
    printf("]\n");
    
    // Free memory
    for (int i = 0; i < m; i++) {
        free(rooms[i]);
    }
    free(rooms);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(mn)

Each cell is visited at most once during BFS traversal

✓ Linear Growth

Space Complexity

O(mn)

Queue can store up to all cells in worst case, plus input grid

⚡ Linearithmic Space

89.2K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Multi-Source BFS (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler