Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Grid & Graph BFS

Guide 3 of 6 · Path 3 of 6

← PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumgrid-graph-bfs

Walls and Gates

Problem (restated)

Grid cells: -1 wall, 0 gate, INF empty. Fill each empty room with distance to nearest gate (in-place).

Intuition

Multi-source BFS from all gates at once; first touch is shortest.

Approaches

Multi-source BFS

Tested only
Time O(m*n)Space O(m*n)

Idea. Enqueue all 0s; expand 4-dir into INF cells writing dist+1.

Walkthrough. Rooms adjacent to a gate become 1, then 2, …

Trade-offs. Multi-source beats BFS-from-each-gate separately.

Solution
export function wallsAndGates(rooms: number[][]): void {
  const m = rooms.length, n = rooms[0]?.length ?? 0;
  const q: [number, number][] = [];
  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      if (rooms[r]![c] === 0) q.push([r, c]);
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  while (q.length) {
    const [r, c] = q.shift()!;
    for (const [dr, dc] of dirs) {
      const nr = r + dr!, nc = c + dc!;
      if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
      if (rooms[nr]![nc] !== 2147483647) continue;
      rooms[nr]![nc] = rooms[r]![c]! + 1;
      q.push([nr, nc]);
    }
  }
}

export function wallsAndGates(rooms: number[][]): void {
  const m = rooms.length, n = rooms[0]?.length ?? 0;
  const q: [number, number][] = [];
  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      if (rooms[r]![c] === 0) q.push([r, c]);
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  while (q.length) {
    const [r, c] = q.shift()!;
    for (const [dr, dc] of dirs) {
      const nr = r + dr!, nc = c + dc!;
      if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
      if (rooms[nr]![nc] !== 2147483647) continue;
      rooms[nr]![nc] = rooms[r]![c]! + 1;
      q.push([nr, nc]);
    }
  }
}

Template connection

Grid multi-source BFS.

Reflection