BFS on grids and implicit graphs

A grid is a graph you never build

The graph chapter stored a graph as an adjacency list: one array of neighbours per node. A grid hands you a graph for free. Every cell is a node, and two cells are joined by an edge when they share a side and neither one is a wall. You do not build any list. The neighbours of (r, c) are (r-1, c), (r+1, c), (r, c-1) and (r, c+1), and you compute them at the moment you need them. A grid with R rows and C columns has R·C nodes and at most 2·R·C − R − C edges, so the V + E of a traversal is O(R·C).

Everything you learned about traversal carries over. BFS visits cells in order of distance, DFS wanders through a region, and a visited marker stops you walking in circles. What is new is bookkeeping and a short list of shapes that return again and again:

• One start, one target, fewest moves is BFS that records a distance for every cell.
• Many starts at once (the nearest gate, the nearest zero, every rotten orange) is multi-source BFS.
• Paint, count or measure a connected region is flood fill, by DFS or BFS.
• Which cells can reach the edge is a search that starts at the edge and runs backward.
• The nodes are not cells at all: words, lock combinations, board positions. It is the same BFS on an implicit graph.

Conventions used throughout: grid[r][c], with r counting rows downward and c counting columns to the right; rows = grid.length and cols = grid[0].length; in the shortest-path examples 0 is an open cell and 1 is a wall unless a problem says otherwise.

Direction arrays and the bounds check

Writing four copies of the same neighbour code, one per direction, is how typos get in. Put the four moves in an array of [dr, dc] pairs and loop. The loop body then exists once, and a change from four directions to eight is a change to the array, not to the algorithm.

const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]]; // up, down, left, right as [dr, dc]

function forEachNeighbor(grid, r, c, visit) {
  const rows = grid.length, cols = grid[0].length;
  for (const [dr, dc] of DIRS) {
    const nr = r + dr, nc = c + dc;
    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue; // bounds BEFORE any grid[nr][nc]
    visit(nr, nc);
  }
}

The rest of the chapter writes that loop inline, because a callback adds noise to code you have to produce on a whiteboard. The order inside DIRS does not change any distance. It changes which of several equally short paths you find, and the order in which cells leave the queue.

A cell is often stored as one number, id = r * cols + c, and recovered with r = Math.floor(id / cols) and c = id % cols. On a grid with 3 columns, cell (2, 1) is id 7. One number is cheaper to put in a Set or an array than a pair, and it is the right key for a Map, as the next warning shows.

BFS gives distances: the layer argument

The task: the fewest moves from a start cell to a goal cell, moving up, down, left or right through open cells. DFS is the wrong tool. It follows one path to the end before trying another, so the first route it finds is whatever its direction order happened to prefer, and checking every route costs time that grows exponentially with the grid size.

Derive the right method from the definition of distance. Exactly one cell is at distance 0: the start. A cell is at distance d + 1 exactly when it is not at a smaller distance and it touches a cell at distance d. So if you know all the cells at distance d, the next layer is every unseen neighbour of that layer. Computing layer by layer is BFS, and a queue is the natural way to keep the current layer and the one being built in order.

Why a queue never mixes layers up: at every moment it holds some cells at distance d followed by some cells at distance d + 1, and nothing else. At the start it holds only the start cell. By the time the first cell at distance d is popped, every cell at distance d is already in the queue, because they were all appended while the cells at distance d − 1 were popped. So an unseen neighbour of a cell at distance d cannot have distance d or less; its distance is exactly d + 1, and it joins the back. That keeps the invariant. The consequence is the one you want: cells leave the queue in non-decreasing order of distance, so the first time any cell is discovered it is discovered through a shortest path, and the number you store for it is final. Nothing ever has to be corrected afterwards.

function shortestPath(grid, start, goal) {
  const rows = grid.length, cols = grid[0].length;
  const [sr, sc] = start, [gr, gc] = goal;
  if (grid[sr][sc] === 1 || grid[gr][gc] === 1) return -1; // start or goal inside a wall

  const dist = Array.from({ length: rows }, () => new Array(cols).fill(-1)); // -1 = not seen yet
  dist[sr][sc] = 0;
  const queue = [[sr, sc]];
  let head = 0; // read position: queue[head++] instead of queue.shift() (see the queue section)

  while (head < queue.length) {
    const [r, c] = queue[head++];
    if (r === gr && c === gc) return dist[r][c];
    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (grid[nr][nc] === 1 || dist[nr][nc] !== -1) continue; // wall, or already has its final distance
      dist[nr][nc] = dist[r][c] + 1; // marked NOW, at enqueue time
      queue.push([nr, nc]);
    }
  }
  return -1; // the queue ran dry: the goal is not reachable
}

The dist matrix does two jobs. It stores the answer, and its -1 is the "seen" flag, so there is no separate visited array. The sentinel is -1 and not 0 because 0 is a real distance: the start cell has it.

Dry run: shortestPath on the grid in the figure, start (0, 0), goal (3, 4)

Read the queue column: it never holds more than two different distances. After pop 8 it holds (2,2) at distance 4 and (3,2) at distance 5, and no third distance ever appears, exactly as the argument said.

Cost. Each cell is enqueued at most once, because the dist check blocks a second entry, and each pop looks at four neighbours. That is O(R·C) time. The dist matrix and the queue are both O(R·C) space in the worst case. The goal test sits at the pop, not at the push, which is simplest and just as correct for BFS: the answer is the same either way, and testing at the push only stops a little earlier.

• If start equals goal and the cell is open, the answer is 0, and the code returns it on the first pop.
• If start or goal is a wall, the answer is -1 before any search begins. Decide this out loud; some statements guarantee it cannot happen.
• A goal that is open but walled in is found by the queue running dry. Returning -1 after the loop is the unreachable case, not an afterthought.

Visited on enqueue, not on dequeue: what goes wrong

The graph chapter told you to mark a node as seen when you push it, not when you pop it. Here is exactly what that rule buys, measured on an open n by n grid searched from a corner. Three policies:

function queueEntriesMarkOnEnqueue(n) {
  const seen = Array.from({ length: n }, () => new Array(n).fill(false));
  seen[0][0] = true;
  const queue = [[0, 0]];
  let head = 0, pushes = 1;
  while (head < queue.length) {
    const [r, c] = queue[head++];
    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= n || nc < 0 || nc >= n || seen[nr][nc]) continue;
      seen[nr][nc] = true; // the cell is claimed the moment it is queued
      queue.push([nr, nc]);
      pushes++;
    }
  }
  return pushes;
}

function queueEntriesMarkOnDequeueGuarded(n) {
  const seen = Array.from({ length: n }, () => new Array(n).fill(false));
  const queue = [[0, 0]];
  let head = 0, pushes = 1;
  while (head < queue.length) {
    const [r, c] = queue[head++];
    if (seen[r][c]) continue; // a duplicate entry: drop it on the way out
    seen[r][c] = true;
    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= n || nc < 0 || nc >= n || seen[nr][nc]) continue;
      queue.push([nr, nc]); // the neighbour is not marked yet, so others can queue it too
      pushes++;
    }
  }
  return pushes;
}

function queueEntriesMarkOnDequeueUnguarded(n) {
  const seen = Array.from({ length: n }, () => new Array(n).fill(false));
  const queue = [[0, 0]];
  let head = 0, pushes = 1;
  while (head < queue.length) {
    const [r, c] = queue[head++];
    seen[r][c] = true; // no "already seen?" test before expanding
    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= n || nc < 0 || nc >= n || seen[nr][nc]) continue;
      queue.push([nr, nc]);
      pushes++;
    }
  }
  return pushes;
}

Each column has a reason, and you should be able to give it.

• Mark on enqueue: a cell is claimed when it is queued, so it is queued once. The number of entries is the number of cells reached, at most R·C.
• Mark on dequeue, with the guard: still correct, because the second copy of a cell is thrown away when it comes out. But until a cell is popped, every neighbour that touches it can queue it again, so the queue holds up to four entries per cell (about two on this grid). On a general graph the bound is the sum of the degrees, 2E, instead of V, which is the difference between a queue the size of the nodes and a queue the size of the edges.
• Mark on dequeue, no guard: every copy of a cell is expanded, and every expansion queues that cell's neighbours again. On an open grid the number of copies of a cell is the number of shortest paths that reach it, which for the cell at row i, column j is C(i + j, i). The total for an n by n grid is C(2n, n) − 1, which is 184,755 at n = 10 and about 1.2 · 10¹⁷ at n = 30. That is the case the phrase "can blow up badly" in the graph chapter was warning about.

Recovering the path with parent pointers

Often the problem wants the route and not just its length. Record, for each cell, the cell it was discovered from. Because a cell is discovered once, it has exactly one parent, and the parents form a tree rooted at the start. The route to any cell is the walk from that cell back to the root, read in reverse.

function shortestRoute(grid, start, goal) {
  const rows = grid.length, cols = grid[0].length;
  const id = (r, c) => r * cols + c;
  const [sr, sc] = start, [gr, gc] = goal;
  if (grid[sr][sc] === 1 || grid[gr][gc] === 1) return null;

  const parent = new Array(rows * cols).fill(-2); // -2 = unseen, -1 = "this is the start"
  parent[id(sr, sc)] = -1;
  const queue = [id(sr, sc)];
  let head = 0;

  while (head < queue.length && parent[id(gr, gc)] === -2) { // stop once the goal has a parent
    const cur = queue[head++];
    const r = Math.floor(cur / cols), c = cur % cols;
    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (grid[nr][nc] === 1 || parent[id(nr, nc)] !== -2) continue;
      parent[id(nr, nc)] = cur;
      queue.push(id(nr, nc));
    }
  }
  if (parent[id(gr, gc)] === -2) return null;

  const route = [];
  for (let at = id(gr, gc); at !== -1; at = parent[at]) {
    route.push([Math.floor(at / cols), at % cols]);
  }
  return route.reverse(); // built goal-first, so flip it
}

Dry run: walking back from the goal (cols = 5, so id = 5r + c)

Reversed, that is (0,0) (0,1) (0,2) (1,2) (2,2) (2,3) (2,4) (3,4): eight cells, seven moves, matching the distance of 7. When several routes tie for shortest, you get the one the direction order discovered first. This grid has exactly one.

Counting layers instead of storing distances

If you only want the length, and not a distance for every cell, process the queue one layer at a time and count the layers. The simplest way to write it is two arrays: the current layer and the next one.

function stepsByLayers(grid, start, goal) {
  const rows = grid.length, cols = grid[0].length;
  const [sr, sc] = start, [gr, gc] = goal;
  if (grid[sr][sc] === 1 || grid[gr][gc] === 1) return -1;

  const seen = Array.from({ length: rows }, () => new Array(cols).fill(false));
  seen[sr][sc] = true;
  let layer = [[sr, sc]];
  let steps = 0; // the layer in hand is at distance "steps"

  while (layer.length > 0) {
    const next = [];
    for (const [r, c] of layer) {
      if (r === gr && c === gc) return steps;
      for (const [dr, dc] of DIRS) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
        if (grid[nr][nc] === 1 || seen[nr][nc]) continue;
        seen[nr][nc] = true;
        next.push([nr, nc]);
      }
    }
    layer = next;
    steps++; // the next layer is one move further out
  }
  return -1;
}

The layer variable is also the right tool when a problem counts time in rounds, as Rotting Oranges does. The one thing to settle before you write it is what the start is worth. A problem that counts moves starts at 0. A problem that counts the cells on the path, or the words in a sequence, starts at 1. Most off-by-one answers in this chapter's problems come from not deciding that first.

A queue without the O(n) shift

Every BFS above reads the queue with queue[head++]. The alternative, queue.shift(), is what most people type first. The language defines it as removing the first element and then moving every remaining element down one index, which is O(n) per call. Engines may speed that up in some situations, but a chapter on complexity cannot rely on an optimisation it cannot see, and the cost shows up at exactly the sizes that grid problems reach. Measure it:

function drainWithShift(n) {
  const items = Array.from({ length: n }, (_, i) => i);
  const begin = performance.now();
  while (items.length > 0) items.shift();
  return performance.now() - begin;
}

function drainWithHead(n) {
  const items = Array.from({ length: n }, (_, i) => i);
  const begin = performance.now();
  let head = 0;
  while (head < items.length) head++;
  return performance.now() - begin;
}

On the machine used to check this chapter, in Node 24, draining 10,000 numbers with shift took a millisecond or two. Draining 100,000 took about a second, and 400,000 took about twenty seconds, while the head index took about a millisecond each time. Your numbers will differ. The lesson is the growth: multiply the size by four and the shift version got many times slower, the direction that a quadratic cost (sixteen times) predicts. A grid of 1000 by 1000 puts a million cells through the queue.

The head index has one cost: the array never shrinks, so it ends up holding every cell ever queued. For a single BFS over a grid that is at most R·C entries, which you were paying for in the dist matrix anyway. For a long-running queue that keeps receiving work, wrap the idea in a small class that drops the consumed prefix from time to time:

class Queue {
  constructor() {
    this.items = [];
    this.head = 0;
  }
  get size() {
    return this.items.length - this.head;
  }
  enqueue(value) {
    this.items.push(value);
  }
  dequeue() {
    if (this.head === this.items.length) return undefined;
    const value = this.items[this.head];
    this.items[this.head] = undefined; // let the consumed value be collected
    this.head++;
    if (this.head >= 32 && this.head * 2 >= this.items.length) {
      this.items = this.items.slice(this.head); // copy only the live half
      this.head = 0;
    }
    return value;
  }
}

Every operation is O(1) amortised. The slice runs only when the consumed prefix is at least half of the array, so it copies no more elements than the number of dequeues since the last copy, and each dequeue pays for one element of copying. The array never holds more than about twice the live elements plus 32.

The other common way to avoid the cost, as in stepsByLayers, is to keep two arrays and swap them each round. If an interviewer pushes on shift, the honest answer has two parts: say that it is O(n) by definition, and that you use a read index so the BFS stays O(V + E). The stacks and queues chapter covers the deque you need when you must also remove from the back.

Multi-source BFS: start from every source at once

The task: for every cell, the distance to the nearest gate. The slow idea is to run one BFS from every gate and keep the minimum for each cell, which costs O(G·R·C) for G gates. The fast idea comes from the layer argument. Nothing in that argument needed the first layer to contain one cell. If you put every gate in the queue at distance 0 before the loop starts, the queue still holds d followed by d + 1, the layers still grow outward one step at a time, and every cell is first reached by whichever gate is nearest to it. One BFS answers all the questions: O(R·C) time, no matter how many gates there are.

Another way to see it: add an imaginary node joined to every gate by an edge of length 0. A normal BFS from that node starts with all the gates, exactly as if they were one source.

function wallsAndGates(rooms) {
  const INF = 2147483647; // an empty room not yet reached; -1 is a wall, 0 is a gate
  const rows = rooms.length;
  if (rows === 0) return rooms;
  const cols = rooms[0].length;

  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]); // every gate starts in the queue
    }
  }

  let head = 0;
  while (head < queue.length) {
    const [r, c] = queue[head++];
    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (rooms[nr][nc] !== INF) continue; // walls, gates and reached rooms are all skipped
      rooms[nr][nc] = rooms[r][c] + 1;
      queue.push([nr, nc]);
    }
  }
  return rooms;
}

Here the grid itself is the seen marker: a cell that still holds INF is unseen, and writing a distance into it claims it. A room that no gate can reach keeps INF, which is the answer the problem asks for. The 01 Matrix problem is the same code with the roles named differently. Every 0 is a source, and the answer for each 1 is the distance to the nearest zero. This version leaves the input alone and returns a new matrix:

function updateMatrix(mat) {
  const rows = mat.length, cols = mat[0].length;
  const dist = Array.from({ length: rows }, () => new Array(cols).fill(-1));
  const queue = [];
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (mat[r][c] === 0) {
        dist[r][c] = 0;
        queue.push([r, c]);
      }
    }
  }

  let head = 0;
  while (head < queue.length) {
    const [r, c] = queue[head++];
    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (dist[nr][nc] !== -1) continue;
      dist[nr][nc] = dist[r][c] + 1;
      queue.push([nr, nc]);
    }
  }
  return dist;
}

Rotting Oranges asks for time instead of distance: all rotten oranges spread at once, and each minute every fresh orange next to a rotten one rots. The minute count is the number of layers, so this one is written with the layer arrays and a count of fresh oranges left:

function orangesRotting(grid) {
  const rows = grid.length, cols = grid[0].length;
  let layer = [];
  let fresh = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) layer.push([r, c]);
      else if (grid[r][c] === 1) fresh++;
    }
  }

  let minutes = 0;
  while (layer.length > 0 && fresh > 0) { // stop the moment nothing fresh is left
    const next = [];
    for (const [r, c] of layer) {
      for (const [dr, dc] of DIRS) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
        if (grid[nr][nc] !== 1) continue;
        grid[nr][nc] = 2; // rot it now, so no other orange can queue it again
        fresh--;
        next.push([nr, nc]);
      }
    }
    layer = next;
    minutes++;
  }
  return fresh === 0 ? minutes : -1; // leftover fresh oranges are unreachable
}

Dry run: orangesRotting on [[2,1,1],[1,1,0],[0,1,1]]

• The condition fresh > 0 in the loop is what keeps minutes honest. Without it the loop runs one more time on a layer that rots nothing, and the answer is 1 too big.
• If there are no fresh oranges at the start, the loop never runs and the answer is 0, as the problem requires.
• If a fresh orange is walled off, the layers run out before fresh reaches 0, and the final line returns -1.
• All sources are queued before the loop. Starting a BFS from one source and adding the others as you meet them gives layers that no longer line up with time.
• This version writes into the input grid. Ask whether you may; if not, copy it first, or keep a separate seen array.

Flood fill: DFS or BFS, and what the stack costs

Flood fill paints the connected region of one colour that contains a given cell. It is the same walk as the traversal chapter, with the grid itself as the visited marker: painting a cell changes its colour away from the old one, so it will not be painted twice. Here it is both ways.

function floodFillDfs(image, sr, sc, color) {
  const rows = image.length, cols = image[0].length;
  const old = image[sr][sc];
  if (old === color) return image; // without this line the paint never changes anything and the recursion never ends

  function paint(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || image[r][c] !== old) return;
    image[r][c] = color;
    paint(r - 1, c);
    paint(r + 1, c);
    paint(r, c - 1);
    paint(r, c + 1);
  }
  paint(sr, sc);
  return image;
}

function floodFillBfs(image, sr, sc, color) {
  const rows = image.length, cols = image[0].length;
  const old = image[sr][sc];
  if (old === color) return image;

  image[sr][sc] = color; // paint on enqueue: painting IS the visited mark
  const queue = [[sr, sc]];
  let head = 0;
  while (head < queue.length) {
    const [r, c] = queue[head++];
    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (image[nr][nc] !== old) continue;
      image[nr][nc] = color;
      queue.push([nr, nc]);
    }
  }
  return image;
}

function floodFillStack(image, sr, sc, color) {
  const rows = image.length, cols = image[0].length;
  const old = image[sr][sc];
  if (old === color) return image;

  image[sr][sc] = color;
  const stack = [[sr, sc]];
  while (stack.length > 0) {
    const [r, c] = stack.pop(); // pop() from the end is O(1); this is DFS with a stack you own
    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (image[nr][nc] !== old) continue;
      image[nr][nc] = color;
      stack.push([nr, nc]);
    }
  }
  return image;
}

All three do O(R·C) work and produce the same image. They differ in what they hold while they work. The recursive one holds a call frame per cell on the current path. A depth-first walk through an open region does not go straight and come back; it snakes. On an open 100 by 100 image, from the top-left corner with the direction order above, the recursive version overflows the stack in Node 24, and a 50 by 50 image is fine. A plain function that only calls itself overflowed at 10,373 frames on the same run, and a function with more locals overflows sooner. The limit depends on the engine and the frame size, so treat "about ten thousand" as the order of magnitude and not as a promise.

The queue version has no such limit, because the queue lives on the heap. On open images measured here the queue held at most 300 cells for a 300 by 300 image painted from a corner, 599 from the centre, and 1000 for a 1000 by 1000 image painted from a corner. That is roughly the length of the frontier, which is much less than the number of cells, though a maze-like region can make it larger. The explicit stack has the same freedom from the call-stack limit and the same O(R·C) bound in the worst case.

Counting regions is flood fill in a loop: scan every cell, and each time you meet an unseen land cell, start a fill, add one to the count, and let the fill claim the whole island. The same code handles both kinds of adjacency, because the directions are a parameter:

function countIslands(grid, dirs = DIRS) {
  const rows = grid.length, cols = grid[0].length;
  const seen = Array.from({ length: rows }, () => new Array(cols).fill(false));
  let islands = 0;

  for (let r0 = 0; r0 < rows; r0++) {
    for (let c0 = 0; c0 < cols; c0++) {
      if (grid[r0][c0] !== "1" || seen[r0][c0]) continue;
      islands++; // an unseen land cell is a new island
      seen[r0][c0] = true;
      const queue = [[r0, c0]];
      let head = 0;
      while (head < queue.length) {
        const [r, c] = queue[head++];
        for (const [dr, dc] of dirs) {
          const nr = r + dr, nc = c + dc;
          if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
          if (grid[nr][nc] !== "1" || seen[nr][nc]) continue;
          seen[nr][nc] = true;
          queue.push([nr, nc]);
        }
      }
    }
  }
  return islands;
}

It uses a seen matrix so the caller's grid is untouched, and it compares to the string "1" because that is how the classic problem gives its input. Check the element type in your problem: comparing "1" to 1 is the usual reason such a solution finds zero islands. Each cell is queued at most once, so the time is O(R·C) and the extra space is O(R·C).

Choosing between the versions is not about speed. If you need distances, use BFS. If you need only membership or an area, either works, and the recursive one is the shortest to write, which is why many interviewers accept it as long as you name the depth risk and know the fix.

Eight directions and other moves

Diagonal moves change only the direction array. Rather than type eight pairs, generate them from the nine combinations of -1, 0 and 1 and drop the one that does not move:

const DIRS8 = [];
for (let dr = -1; dr <= 1; dr++) {
  for (let dc = -1; dc <= 1; dc++) {
    if (dr !== 0 || dc !== 0) DIRS8.push([dr, dc]);
  }
}

function shortestPathBinaryMatrix(grid) {
  const n = grid.length;
  if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) return -1;

  const dist = Array.from({ length: n }, () => new Array(n).fill(0)); // 0 = unseen, because the start counts as 1
  dist[0][0] = 1; // the answer counts cells, so the start is cell number 1
  const queue = [[0, 0]];
  let head = 0;
  while (head < queue.length) {
    const [r, c] = queue[head++];
    if (r === n - 1 && c === n - 1) return dist[r][c];
    for (const [dr, dc] of DIRS8) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
      if (grid[nr][nc] === 1 || dist[nr][nc] !== 0) continue;
      dist[nr][nc] = dist[r][c] + 1;
      queue.push([nr, nc]);
    }
  }
  return -1;
}

The algorithm is unchanged. Time is O(8·R·C), which is O(R·C). Three details matter. First, every move costs one, so a diagonal step counts the same as a side step. BFS is only correct when all moves cost the same. If a diagonal costs more, the layers stop meaning "d moves" and you need Dijkstra's algorithm from the advanced graph chapter. Second, the problem decides whether a path may slip diagonally between two walls that touch at a corner. The classic statement allows it; ask when it is not stated. Third, the same array switches island counting from 4-connected to 8-connected, as the dirs parameter above shows.

Other move sets are other arrays or other neighbour functions, and BFS does not care:

Reverse from the borders

Some questions ask about every cell: which cells can send water to both oceans, which regions are completely surrounded. The direct way to answer such a question is to start a search from each cell and see where it ends up. That is a search of up to R·C cells, repeated R·C times: O(R²·C²).

The trick is to turn the question around. Water in Pacific Atlantic Water Flow moves from a cell to a neighbour that is not higher. A cell reaches the Pacific exactly when a non-increasing path leads from it to the top or left edge. Read that path backward and it is a non-decreasing path from the edge to the cell. So instead of asking, for each cell, "can it reach the edge?", start at the edge cells and ask once, "which cells can be reached by climbing?" That is a multi-source BFS from the whole border, with the neighbour rule reversed. Do it once for each ocean and keep the cells that appear in both.

function reachFrom(heights, starts) {
  const rows = heights.length, cols = heights[0].length;
  const seen = Array.from({ length: rows }, () => new Array(cols).fill(false));
  const queue = [];
  for (const [r, c] of starts) {
    if (!seen[r][c]) {
      seen[r][c] = true;
      queue.push([r, c]);
    }
  }

  let head = 0;
  while (head < queue.length) {
    const [r, c] = queue[head++];
    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (seen[nr][nc] || heights[nr][nc] < heights[r][c]) continue; // reversed: only climb or stay level
      seen[nr][nc] = true;
      queue.push([nr, nc]);
    }
  }
  return seen;
}

function pacificAtlantic(heights) {
  const rows = heights.length, cols = heights[0].length;
  const pacificEdge = [], atlanticEdge = [];
  for (let r = 0; r < rows; r++) {
    pacificEdge.push([r, 0]);
    atlanticEdge.push([r, cols - 1]);
  }
  for (let c = 0; c < cols; c++) {
    pacificEdge.push([0, c]);
    atlanticEdge.push([rows - 1, c]);
  }
  const pacific = reachFrom(heights, pacificEdge);
  const atlantic = reachFrom(heights, atlanticEdge);

  const both = [];
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (pacific[r][c] && atlantic[r][c]) both.push([r, c]);
    }
  }
  return both;
}

Dry run: the classic 5 by 5 example

Heights. Below, P marks a cell the Pacific search reaches, A one the Atlantic search reaches, PA both, and a dot neither.

The seven cells marked PA are the answer: (0,4), (1,3), (1,4), (2,2), (3,0), (3,1) and (4,0). Take (2,2), height 5. The Pacific search reaches it by climbing from (2,0) at height 2 to (2,1) at 4 to (2,2) at 5. The Atlantic search reaches it from the bottom row, climbing from (4,2) at height 1 to (3,2) at 1 to (2,2) at 5. Both searches mark it, so water on (2,2) can flow to either ocean. Each search is one BFS, so the total is O(R·C).

Surrounded Regions has the same shape. Given a board of "X" and "O", flip every "O" region that is completely surrounded by "X". Asking of each region "is it enclosed?" needs a search per region and a way to decide, and that is awkward. Ask the reverse: an "O" survives exactly when it is connected to an "O" on the border. So mark everything reachable from a border "O" as safe, and flip what is left.

function solveSurrounded(board) {
  const rows = board.length, cols = board[0].length;
  const queue = [];
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      const onBorder = r === 0 || r === rows - 1 || c === 0 || c === cols - 1;
      if (onBorder && board[r][c] === "O") {
        board[r][c] = "S"; // S = safe: connected to the border
        queue.push([r, c]);
      }
    }
  }

  let head = 0;
  while (head < queue.length) {
    const [r, c] = queue[head++];
    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (board[nr][nc] !== "O") continue;
      board[nr][nc] = "S";
      queue.push([nr, nc]);
    }
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (board[r][c] === "O") board[r][c] = "X"; // an O nobody marked is enclosed
      else if (board[r][c] === "S") board[r][c] = "O"; // restore the safe ones
    }
  }
  return board;
}

On the board X X X X / X O O X / X X O X / X O X X, the only border "O" is the one at row 3, column 1, and it has no "O" neighbours. The three "O" cells in the middle become "X", and the border one stays. Note the order of the three passes: marking must finish before any flip, because a flip made while you are still marking could cut off a region the search has not reached yet. A third marker value is what lets one pass tell "untouched" from "safe".

The recognition rule: when the question is about the cells that can, or cannot, get out to the boundary, search from the boundary inward instead. Counting enclaves, and finding the cells a flood cannot reach, fit the same frame.

State-space BFS: the graph lives in your head

BFS never needed a grid. It needs states, a rule for the next states, and a test for the goal. A state is whatever fully describes where you are, and fewest moves becomes a shortest path in a graph that you never write down. The generic version takes those three pieces as arguments:

function bfsDistance(start, isGoal, nextStates) {
  const dist = new Map([[start, 0]]);
  const queue = [start];
  let head = 0;
  while (head < queue.length) {
    const state = queue[head++];
    if (isGoal(state)) return dist.get(state);
    for (const next of nextStates(state)) {
      if (dist.has(next)) continue; // the Map is both the distance table and the seen set
      dist.set(next, dist.get(state) + 1);
      queue.push(next);
    }
  }
  return -1;
}

One rule makes it work: the state must be a primitive that compares by value, such as a string or a number. A state held in an array or object would be compared by identity, and the seen check would never match. If the natural state is a tuple, turn it into a string or a number.

Open the lock

A lock has four wheels, each with the digits 0 to 9, starting at "0000". One move turns one wheel by one step, up or down, and 9 wraps to 0. Some combinations are dead ends: reaching one jams the lock. Return the fewest moves to the target, or -1. The state is the four-character string. There are 10,000 states, each with 8 neighbours, so the whole graph has 80,000 directed edges and BFS is cheap. A dead end is simply a state that is never offered as a neighbour.

function openLock(deadends, target) {
  const dead = new Set(deadends);
  if (dead.has("0000")) return -1; // the start itself is jammed
  return bfsDistance(
    "0000",
    (state) => state === target,
    (state) => {
      const out = [];
      for (let i = 0; i < 4; i++) {
        const digit = Number(state[i]);
        for (const turn of [1, 9]) { // +1 and -1 mod 10, written as +1 and +9
          const next = state.slice(0, i) + ((digit + turn) % 10) + state.slice(i + 1);
          if (!dead.has(next)) out.push(next);
        }
      }
      return out;
    }
  );
}

Strings are immutable in JavaScript, so a changed wheel is built with slice around it. If the target is a dead end the search never offers it and the answer is -1. If the target is "0000" and the start is not dead, the answer is 0.

Minimum genetic mutation

A gene is a string over A, C, G and T. A mutation changes one letter, and a mutated gene is allowed only if it is in the bank. Return the fewest mutations from the start gene to the end gene, or -1. The state is the gene. The next states are the one-letter changes that appear in the bank. The length is fixed (8 in the original problem), so each state has at most 3 times the length of candidates.

function minMutation(startGene, endGene, bank) {
  if (startGene === endGene) return 0;
  const valid = new Set(bank);
  if (!valid.has(endGene)) return -1;
  return bfsDistance(
    startGene,
    (gene) => gene === endGene,
    (gene) => {
      const out = [];
      for (let i = 0; i < gene.length; i++) {
        for (const letter of "ACGT") {
          if (letter === gene[i]) continue;
          const next = gene.slice(0, i) + letter + gene.slice(i + 1);
          if (valid.has(next)) out.push(next);
        }
      }
      return out;
    }
  );
}

Snakes and ladders

An n by n board has squares numbered 1 to n² in a zig-zag, starting at the bottom-left corner: the bottom row runs left to right, the next row up runs right to left, and so on. From square s you roll 1 to 6 and land on s + roll, if that is at most n². If the landing square holds a snake or a ladder, you are carried to its far end, and you do not follow a second one from there. Return the fewest rolls to reach square n², or -1. The state is the square you stand on after any jump. The next states are the six landings.

The only hard part is turning a square number into a cell of the 2D array. Count rows from the bottom: row-from-bottom is Math.floor((s - 1) / n), the offset along that row is (s - 1) % n, and every second row runs the other way.

function snakesAndLadders(board) {
  const n = board.length, last = n * n;

  function cellOf(square) {
    const fromBottom = Math.floor((square - 1) / n);
    const offset = (square - 1) % n;
    const r = n - 1 - fromBottom;
    const c = fromBottom % 2 === 0 ? offset : n - 1 - offset; // odd rows from the bottom run right to left
    return [r, c];
  }

  const dist = new Array(last + 1).fill(-1);
  dist[1] = 0;
  const queue = [1];
  let head = 0;
  while (head < queue.length) {
    const square = queue[head++];
    if (square === last) return dist[square];
    for (let roll = 1; roll <= 6 && square + roll <= last; roll++) {
      const [r, c] = cellOf(square + roll);
      const landing = board[r][c] === -1 ? square + roll : board[r][c]; // one jump, not a chain
      if (dist[landing] !== -1) continue;
      dist[landing] = dist[square] + 1;
      queue.push(landing);
    }
  }
  return -1;
}

Dry run: the 6 by 6 board with a ladder 2 → 15, a ladder 14 → 35 and a snake 17 → 13

Square 7 sits above square 6, and square 12 sits above square 1: the second row from the bottom runs right to left.

A shortest route is rolls 6, 6, 1, 1: 1 → 7 → 13 → 14, which is carried to 35 → 36. The ladder at square 2 looks attractive and is a trap here: it lands on 15, and from 15 the goal is 21 squares away, which takes at least four more rolls. The winning route never lands on square 2.

Word ladder: the neighbour function is the whole problem

Change one letter at a time to turn beginWord into endWord, where every intermediate word must be in the list. Return the number of words in the shortest sequence, or 0. The state is a word and the start is worth 1. The goal is the neighbour function. The direct way compares the current word with every word in the list, which is O(N·L) per word and O(N²·L) overall for N words of length L.

The better way uses the idea that two words are neighbours exactly when they agree after one position is blanked out. Replace each position of each word by a wildcard, "*", and group the words by the resulting pattern: hot goes under *ot, h*t and ho*. Two words in the same bucket differ in at most that one position, so a bucket is a clique of neighbours. To find the neighbours of a word, look up its L patterns, and read the buckets.

function wildcardBuckets(beginWord, words) {
  const buckets = new Map();
  for (const word of new Set([beginWord, ...words])) {
    for (let i = 0; i < word.length; i++) {
      const key = word.slice(0, i) + "*" + word.slice(i + 1);
      if (!buckets.has(key)) buckets.set(key, []);
      buckets.get(key).push(word);
    }
  }
  return buckets;
}

function ladderLength(beginWord, endWord, wordList) {
  const words = new Set(wordList);
  if (!words.has(endWord)) return 0; // the end word must be in the list
  const buckets = wildcardBuckets(beginWord, words);

  const dist = new Map([[beginWord, 1]]); // words in the sequence, so the start is 1
  const queue = [beginWord];
  let head = 0;
  while (head < queue.length) {
    const word = queue[head++];
    if (word === endWord) return dist.get(word);
    for (let i = 0; i < word.length; i++) {
      const key = word.slice(0, i) + "*" + word.slice(i + 1);
      for (const next of buckets.get(key)) {
        if (dist.has(next)) continue;
        dist.set(next, dist.get(word) + 1);
        queue.push(next);
      }
    }
  }
  return 0;
}

Dry run: hit to cog with the list hot, dot, dog, lot, log, cog

• Cost. Building the buckets creates N·L keys of length L, so O(N·L²) time and space. The search looks at L buckets per word. A bucket holds only words that differ at one position, so with a 26-letter alphabet it holds at most 26 words, and the search adds O(26·N·L) more steps. The total is O(N·L²), against O(N²·L) for comparing pairs, which is far better when the list is long and the words are short.
• If beginWord is not in the list it is still a legal start, so it goes into the buckets as well, which is why wildcardBuckets adds it.
• If endWord is missing from the list, the answer is 0 at once.

When the state is more than the position

Shortest Path with Obstacle Elimination gives a grid where you may remove up to k walls on your way from the top-left to the bottom-right. A cell alone is not a state. Arriving at the same cell with 3 removals left is better than arriving with 0, so a visited mark on the cell would reject the better arrival and give a wrong answer. The state is the triple (r, c, removals left), and the visited set holds triples.

function shortestPathWithEliminations(grid, k) {
  const rows = grid.length, cols = grid[0].length;
  if (k >= rows + cols - 2) return rows + cols - 2; // enough removals to walk straight: any monotone path is allowed

  const width = k + 1;
  const seen = new Uint8Array(rows * cols * width); // one flag per (cell, removals left)
  seen[k] = 1;
  const queue = [[0, 0, k, 0]]; // row, column, removals left, steps taken
  let head = 0;
  while (head < queue.length) {
    const [r, c, left, steps] = queue[head++];
    if (r === rows - 1 && c === cols - 1) return steps;
    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      const nextLeft = left - grid[nr][nc]; // a wall costs one removal, an open cell costs none
      if (nextLeft < 0) continue;
      const key = (nr * cols + nc) * width + nextLeft;
      if (seen[key]) continue;
      seen[key] = 1;
      queue.push([nr, nc, nextLeft, steps + 1]);
    }
  }
  return -1;
}

There are R·C·(k+1) states and four moves from each, so the time and space are O(R·C·k). The early return is valid because a path that goes only right and down has R + C − 2 steps and passes through at most R + C − 3 cells other than the two ends, so with k at least R + C − 2 even a grid full of walls does not stop it. The code assumes the start and end cells are open, as the problem states.

Bidirectional BFS

A single BFS from the start explores every state within distance d of it before it finds a goal at distance d. How many states is that? It depends on how fast the ball of states within distance k grows. When it grows by a factor b per layer, as in a word ladder with many neighbours, the ball holds about b^d states. Now search from both ends, each to depth d/2. Each ball holds about b^d/2 states, and the two together hold 2·b^d/2, which is dramatically fewer when b is large.

The algorithm keeps two searches, each with its own distance map and its own current layer. Each round, expand one whole layer of the side that currently has the smaller frontier. The moment a neighbour you generate is already in the other side's map, the two searches have met, and the answer is the distance to the state you came from, plus one, plus the other side's distance to the neighbour.

function bidirectionalDistance(start, goal, neighborsOf) {
  if (start === goal) return 0;
  const distA = new Map([[start, 0]]);
  const distB = new Map([[goal, 0]]);
  let frontA = [start], frontB = [goal];

  while (frontA.length > 0 && frontB.length > 0) {
    const growA = frontA.length <= frontB.length; // expand the smaller side
    const front = growA ? frontA : frontB;
    const mine = growA ? distA : distB;
    const other = growA ? distB : distA;
    const next = [];
    for (const state of front) {
      for (const neighbor of neighborsOf(state)) {
        if (other.has(neighbor)) return mine.get(state) + 1 + other.get(neighbor); // the searches met
        if (mine.has(neighbor)) continue;
        mine.set(neighbor, mine.get(state) + 1);
        next.push(neighbor);
      }
    }
    if (growA) frontA = next;
    else frontB = next;
  }
  return -1; // one side ran out of states without meeting the other
}

Why the first meeting is the shortest distance. Let L be the true distance. Each round expands one layer on one side, so the sum of the two sides' depths grows by exactly one per round, starting from 0. Say the layer being expanded is at depth p and the other side's map reaches depth q. A meeting found in that round is a real path of length p + 1 + q', where q' is at most q, so it is at least L and at most p + q + 1. That already shows no meeting can happen while p + q + 1 is less than L. And when p + q + 1 equals L, take a shortest path: its state at distance p from the expanding end is in the layer being expanded, and the next state on the path is at distance q from the other end, so it is already in the other map. That round must find a meeting, and any meeting it finds has length at most L and at least L, so it is exactly L. Which side you expand changes only how many states you visit, never the answer.

The same function runs a word ladder when its neighbour function reads the wildcard buckets:

function ladderLengthBidirectional(beginWord, endWord, wordList) {
  const words = new Set(wordList);
  if (!words.has(endWord)) return 0;
  const buckets = wildcardBuckets(beginWord, words);

  const neighborsOf = (word) => {
    const out = [];
    for (let i = 0; i < word.length; i++) {
      for (const next of buckets.get(word.slice(0, i) + "*" + word.slice(i + 1))) {
        if (next !== word) out.push(next);
      }
    }
    return out;
  };
  const steps = bidirectionalDistance(beginWord, endWord, neighborsOf);
  return steps === -1 ? 0 : steps + 1; // moves become words in the sequence
}

How much does it save? Count the states each search expands (the calls to the neighbour function) on the lock with no dead ends, and on a 20 by 20 open grid:

The lock graph has only 10,000 states, so the far target "5555" is close to the size of the whole graph, and neither search can save much. The middle rows are the case it helps. The corner-to-corner grid saves almost nothing: the goal is the far corner, so the single search ends up covering the whole 20 by 20 grid, and the two searches, each reaching halfway from its own corner, cover half of the grid apiece, the same cells between them. On a grid the ball grows only as the square of the radius, so there is little to gain. Reach for it when the number of states grows quickly with distance and you know the goal state, as in word ladder. Do not expect it to help much on a plain grid.

Choosing the technique, and what each costs

The "square root" in the bidirectional row is a rule of thumb for graphs whose ball size multiplies at each layer. It is not a bound for every graph, as the grid row of the previous table showed.

Recognizing it in an unseen problem

• "Minimum number of steps, moves, turns or mutations" and every step costs the same: BFS. Ask what the state is and what its neighbours are.
• A 2D array where you move to adjacent cells: a grid graph. Ask first whether diagonals are allowed and what blocks a move.
• "Nearest", "closest" or "as far as possible from" a set of cells: multi-source BFS, with the set as the first layer.
• Everything happens at once, each round or minute: layers, and count them.
• "Which cells can reach the border", "enclosed", "cannot escape": start at the border and run the rule backward.
• The input is words, a lock, a board position, a puzzle: write the state as a string, enumerate the neighbours, and the rest is the code from this chapter.
• The answer depends on something besides the position, such as removals left, keys held, or direction: add it to the state.
• Not BFS: costs that differ per move (use Dijkstra), longest paths, or counting every path (DFS with memoization or DP).