Skip to main content

286. Walls and Gates

mediumAsked at Snap

Snap Maps uses a similar multi-source BFS to compute the minimum walking distance from every map cell to the nearest point of interest — walls and gates is the canonical warmup for that spatial query.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given an m x n grid initialized with three possible values: -1 (wall), 0 (gate), or INF = 2^31-1 (empty room). Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, leave it as INF.

Constraints

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

Examples

Example 1

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

Example 2

Input
rooms = [[-1]]
Output
[[-1]]

Approaches

1. Single-source BFS per gate (naive)

For each gate, run BFS and update distances. O(k * m * n) where k = number of gates. Redundant work when gates are dense.

Time
O(k * m * n)
Space
O(m * n)
function wallsAndGates(rooms) {
  const m = rooms.length, n = rooms[0].length;
  const INF = 2147483647;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  function bfs(sr, sc) {
    const queue = [[sr, sc, 0]];
    while (queue.length) {
      const [r, c, dist] = queue.shift();
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < m && nc >= 0 && nc < n && rooms[nr][nc] === INF) {
          rooms[nr][nc] = dist + 1;
          queue.push([nr, nc, dist + 1]);
        }
      }
    }
  }
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (rooms[r][c] === 0) bfs(r, c);
    }
  }
}

Tradeoff:

2. Multi-source BFS from all gates simultaneously

Seed the queue with every gate at distance 0, then expand in BFS order. Each cell is visited at most once — the first time it's reached guarantees minimum distance from any gate. O(m*n) total.

Time
O(m*n)
Space
O(m*n)
function wallsAndGates(rooms) {
  const m = rooms.length, n = rooms[0].length;
  const INF = 2147483647;
  const queue = [];
  // Seed with all gates
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (rooms[r][c] === 0) queue.push([r, c]);
    }
  }
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  let i = 0;
  while (i < queue.length) {
    const [r, c] = queue[i++];
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < m && nc >= 0 && nc < n && rooms[nr][nc] === INF) {
        rooms[nr][nc] = rooms[r][c] + 1;
        queue.push([nr, nc]);
      }
    }
  }
}

Tradeoff:

Snap-specific tips

Snap Maps engineers describe this as 'nearest POI distance field.' The multi-source BFS insight — seed from all sources at once rather than per source — is the key differentiator Snap looks for. Also discuss how you'd handle real-time gate additions (incremental BFS from the new gate only).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Walls and Gates and other Snap interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →