Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

286. Walls and Gates - Leetcode Solution

Code Implementation

from collections import deque

class Solution:
    def wallsAndGates(self, rooms):
        if not rooms or not rooms[0]:
            return
        m, n = len(rooms), len(rooms[0])
        queue = deque()
        for i in range(m):
            for j in range(n):
                if rooms[i][j] == 0:
                    queue.append((i, j))
        directions = [(-1,0), (1,0), (0,-1), (0,1)]
        while queue:
            x, y = queue.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and rooms[nx][ny] == 2147483647:
                    rooms[nx][ny] = rooms[x][y] + 1
                    queue.append((nx, ny))
      
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        int m = rooms.size();
        if (m == 0) return;
        int n = rooms[0].size();
        queue<pair<int, int>> q;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (rooms[i][j] == 0)
                    q.push({i, j});
            }
        }
        vector<pair<int, int>> directions = {{-1,0},{1,0},{0,-1},{0,1}};
        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            for (auto dir : directions) {
                int nx = x + dir.first, ny = y + dir.second;
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && rooms[nx][ny] == 2147483647) {
                    rooms[nx][ny] = rooms[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }
};
      
import java.util.*;

class Solution {
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0) return;
        int m = rooms.length, n = rooms[0].length;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                }
            }
        }
        int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            for (int[] dir : directions) {
                int nx = curr[0] + dir[0];
                int ny = curr[1] + dir[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && rooms[nx][ny] == Integer.MAX_VALUE) {
                    rooms[nx][ny] = rooms[curr[0]][curr[1]] + 1;
                    queue.offer(new int[]{nx, ny});
                }
            }
        }
    }
}
      
/**
 * @param {number[][]} rooms
 * @return {void} Do not return anything, modify rooms in-place instead.
 */
var wallsAndGates = function(rooms) {
    if (!rooms || rooms.length === 0) return;
    const m = rooms.length, n = rooms[0].length;
    const queue = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (rooms[i][j] === 0) queue.push([i, j]);
        }
    }
    const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
    while (queue.length) {
        const [x, y] = queue.shift();
        for (const [dx, dy] of dirs) {
            const nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && rooms[nx][ny] === 2147483647) {
                rooms[nx][ny] = rooms[x][y] + 1;
                queue.push([nx, ny]);
            }
        }
    }
};

Problem Description

The "Walls and Gates" problem asks you to fill each empty room in a 2D grid with the distance to its nearest gate. The grid is represented by a matrix rooms where:

  • -1 represents a wall or obstacle
  • 0 represents a gate
  • 2147483647 (i.e., INF) represents an empty room
The goal is to fill each empty room with the number of steps to the nearest gate. If a gate is unreachable, leave the value as INF. You must update the rooms grid in-place.

Thought Process

At first glance, it might seem natural to start from each empty room and search for the nearest gate. However, this brute-force approach would require searching for every empty cell, leading to redundant searches and inefficiency.

Instead, it's more efficient to reverse the process: start from all gates and expand outward. This way, we can use a breadth-first search (BFS) to propagate the minimum distance to each room, ensuring that each cell is updated with the shortest possible path to a gate. This is similar to how waves ripple out from multiple sources at once.

Solution Approach

  • Step 1: Traverse the grid and enqueue the coordinates of all gates (0 cells).
  • Step 2: Use a queue to perform BFS, starting from all gates simultaneously. This ensures that the first time we reach an empty room, it's via the shortest path from a gate.
  • Step 3: For each cell dequeued, check its four neighbors (up, down, left, right). If a neighbor is an empty room (INF), update its value to the current cell's value + 1 and enqueue its coordinates.
  • Step 4: Repeat until the queue is empty, meaning all reachable rooms have been updated with their minimum distance to a gate.
  • Why this works: BFS guarantees the shortest path in an unweighted grid. By starting from all gates, we avoid redundant work and ensure every room is filled with the minimum distance to any gate.

Example Walkthrough

Consider the following grid (INF = 2147483647): 

  [
    [INF,  -1,   0, INF],
    [INF, INF, INF,  -1],
    [INF,  -1, INF,  -1],
    [  0,  -1, INF, INF]
  ]

Step-by-step:

  1. All gates at (0,2) and (3,0) are enqueued.
  2. From (0,2), update (0,3) and (1,2) to 1. From (3,0), update (2,0) to 1.
  3. Continue BFS: update (1,3), (1,1), (2,2), (3,2), etc., increasing the distance by 1 each time.
  4. Eventually, all reachable rooms have their minimum distance to the nearest gate. Unreachable rooms (blocked by walls) remain INF.

The final grid: 

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

Time and Space Complexity

  • Brute-force approach: For each empty room, search for the nearest gate, leading to O((mn) * (mn)) time, where m and n are grid dimensions.
  • Optimized BFS approach: Each cell is visited at most once, so the time complexity is O(mn). Each cell may be enqueued and dequeued at most once.
  • Space complexity: O(mn) for the queue in the worst case (if all rooms are empty).

Summary

By reversing the brute-force intuition and starting BFS from all gates, we efficiently fill each empty room with the shortest distance to a gate. This approach leverages the properties of BFS to guarantee minimal distances and avoids unnecessary repeated work, resulting in an elegant and optimal solution for the Walls and Gates problem.