← Back to DevBytes
JavaScript August 08, 2026 7 min read

Solving Walls and Gates in JavaScript: Step-by-Step Guide

Solving Walls and Gates in JavaScript: Step-by-Step Guide

The Walls and Gates problem is a classic graph traversal challenge that frequently appears in coding interviews and real-world spatial reasoning applications. It asks you to compute the shortest distance from every empty room in a grid to the nearest gate, while treating walls as impassable obstacles. In this tutorial, we'll break down the problem, understand why a naive approach fails, and build an optimal solution using multi-source Breadth-First Search (BFS) in JavaScript.

What Is the Walls and Gates Problem?

Imagine a 2D grid representing a building floor plan. Each cell in the grid is one of three things:

Your task is to modify the grid in place so that every empty room contains the distance to the nearest gate. If a room cannot reach any gate (because it's surrounded by walls), it should remain INF.

Here's an example input:

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

And the expected output:

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

Why This Problem Matters

Beyond being a popular interview question, the Walls and Gates problem models several real-world scenarios:

The problem also teaches a crucial algorithmic pattern: multi-source BFS. Instead of running BFS from every room to find a gate (which is expensive), you run BFS once starting from all gates simultaneously. This dramatically reduces the time complexity.

Understanding the Naive Approach and Its Flaws

A first instinct might be to iterate over every empty room and run BFS from that room until you find a gate. While correct, this approach is inefficient. If the grid has m × n cells, and each BFS explores the entire grid in the worst case, the total time complexity becomes O((m × n)²). For a 250 × 250 grid, that's billions of operations.

The key insight is to reverse the perspective. Instead of asking "how far is this room from a gate?", ask "how far does each gate reach?" By starting BFS from every gate at the same time, each cell is visited exactly once, and the first time a cell is reached, it's guaranteed to be via the shortest path from the nearest gate.

Step-by-Step: Multi-Source BFS Solution

Here's the plan:

Because BFS explores cells in order of increasing distance, the first time we reach a room, we've found its shortest distance to a gate. Walls (-1) and already-visited rooms are simply skipped.

The Complete JavaScript Implementation

/**
 * Fills each empty room with the distance to its nearest gate.
 * Modifies the grid in place.
 * @param {number[][]} rooms - The grid of rooms, walls, and gates.
 */
function wallsAndGates(rooms) {
  if (!rooms || rooms.length === 0) return;

  const ROWS = rooms.length;
  const COLS = rooms[0].length;
  const INF = 2147483647;

  // Directions: up, down, left, right
  const directions = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1]
  ];

  // Initialize the queue with all gate positions
  const queue = [];
  for (let r = 0; r < ROWS; r++) {
    for (let c = 0; c < COLS; c++) {
      if (rooms[r][c] === 0) {
        queue.push([r, c]);
      }
    }
  }

  // Multi-source BFS
  while (queue.length > 0) {
    const [r, c] = queue.shift();

    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;

      // Skip out-of-bounds cells
      if (nr < 0 || nr >= ROWS || nc < 0 || nc >= COLS) continue;

      // Only update unvisited empty rooms
      if (rooms[nr][nc] === INF) {
        rooms[nr][nc] = rooms[r][c] + 1;
        queue.push([nr, nc]);
      }
    }
  }
}

// Example usage
const grid = [
  [2147483647, -1, 0, 2147483647],
  [2147483647, 2147483647, 2147483647, -1],
  [2147483647, -1, 2147483647, -1],
  [0, -1, 2147483647, 2147483647]
];

wallsAndGates(grid);
console.log(grid);
// Output:
// [
//   [3, -1, 0, 1],
//   [2, 2, 1, -1],
//   [1, -1, 2, -1],
//   [0, -1, 3, 4]
// ]

Optimizing the Queue with a Head Pointer

The implementation above uses queue.shift(), which is O(n) in JavaScript because it re-indexes the entire array. For large grids, this becomes a bottleneck. A simple optimization is to use an index pointer to track the front of the queue instead of removing elements:

function wallsAndGatesOptimized(rooms) {
  if (!rooms || rooms.length === 0) return;

  const ROWS = rooms.length;
  const COLS = rooms[0].length;
  const INF = 2147483647;
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  const queue = [];
  for (let r = 0; r < ROWS; r++) {
    for (let c = 0; c < COLS; c++) {
      if (rooms[r][c] === 0) {
        queue.push([r, c]);
      }
    }
  }

  let head = 0;
  while (head < queue.length) {
    const [r, c] = queue[head];
    head++;

    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;

      if (nr < 0 || nr >= ROWS || nc < 0 || nc >= COLS) continue;
      if (rooms[nr][nc] === INF) {
        rooms[nr][nc] = rooms[r][c] + 1;
        queue.push([nr, nc]);
      }
    }
  }
}

This small change keeps each enqueue and dequeue operation at O(1), making the overall BFS truly linear with respect to the number of cells.

Complexity Analysis

Let m be the number of rows and n be the number of columns:

Compare this to the naive single-source-per-room approach at O((m × n)²), and the advantage of multi-source BFS becomes clear.

Best Practices and Common Pitfalls

Testing Your Solution

Here's a small test suite covering common scenarios:

function runTests() {
  // Test 1: Standard grid
  const grid1 = [
    [2147483647, -1, 0, 2147483647],
    [2147483647, 2147483647, 2147483647, -1],
    [2147483647, -1, 2147483647, -1],
    [0, -1, 2147483647, 2147483647]
  ];
  wallsAndGates(grid1);
  console.log(JSON.stringify(grid1[0]) === '[3,-1,0,1]');

  // Test 2: No gates
  const grid2 = [[2147483647, -1], [-1, 2147483647]];
  wallsAndGates(grid2);
  console.log(grid2[0][0] === 2147483647 && grid2[1][1] === 2147483647);

  // Test 3: Single gate
  const grid3 = [[0]];
  wallsAndGates(grid3);
  console.log(grid3[0][0] === 0);

  // Test 4: Unreachable room
  const grid4 = [
    [2147483647, -1, 0],
    [-1, -1, -1],
    [2147483647, -1, 2147483647]
  ];
  wallsAndGates(grid4);
  console.log(grid4[2][2] === 2147483647); // surrounded by walls

  // Test 5: Empty input
  wallsAndGates(null);
  wallsAndGates([]);
  console.log('Empty input handled without errors');
}

runTests();

Variations and Follow-Up Questions

Once you understand the core solution, consider these extensions that interviewers often ask:

Conclusion

The Walls and Gates problem is a perfect showcase for the power of multi-source BFS. By flipping the problem on its head and propagating outward from gates instead of searching outward from rooms, you turn a quadratic solution into a linear one. The JavaScript implementation is compact, but the underlying insight — that BFS from all sources simultaneously guarantees shortest paths — is a technique you'll reuse across countless graph problems. Master this pattern, guard against common pitfalls like shift() inefficiency and missing edge cases, and you'll be well equipped to tackle any grid-based distance problem that comes your way.

🛠 Tools from DevBytes

Inventory Tracker Pro — Excel inventory system, low-stock alerts · $19
AI Dev Kit for Mac — local AI dev environment templates · $9.99
KeyMapper for Mac — custom keyboard shortcut toolkit · $7.99

← Back to all articles