/Projects
Coding patterns · 09 of 15

BFS and DFS

Explore grids and graphs; BFS gives shortest steps.

PracticeCoding patternTier 2 · MechanismsApply15 minCore engineering

You will be able to: spot bfs and dfs from a problem statement, and code it from memory.

Interview prepCoding patterns

Study with AI

O(V + E) time, O(V) space Watch as reels
Part 1 of 5

Basics

The idea behind the pattern, why it is correct, and the clues in a question that point to it.

1.1Core idea

What the pattern does, in plain words.

DFS goes deep and is easy for counting regions. BFS explores in layers, so the first time you reach a node is via the fewest steps. Always mark visited when you enqueue.

Why it works

BFS explores in layers: everything one step away, then two steps, and so on, so the first time it reaches a node is along a shortest path in an unweighted graph. DFS goes deep first and is the simpler choice for 'visit everything connected', such as counting islands.

Typical cost: O(V + E) time, O(V) space

1.2Recognition signals

If a question has one of these clues, try this pattern first.

Grids of cells, islands, regionsShortest path with equal edge weightsConnected componentsSpreading over time (rotting oranges)
Part 2 of 5

Question

A classic interview problem from this family. Read it carefully and plan the approach before writing any code.

2.1Number of Islands

The problem statement, then the plan you would say out loud.

Problem

Count groups of connected '1' cells in a grid.

Plan before you code

  1. Scan every cell.
  2. On an unvisited land cell, count an island and flood-fill it.
  3. Flood-fill sinks cells so they are not counted again.
Part 3 of 5

Detailed answer

First the reusable template, then the worked solution built from it and a walk through it one step at a time.

3.1Template

Memorise this shape. Most problems in this family are this code plus one twist.

BFS shortest steps in a grid

bfs-shortest-steps.tsTypeScript
1function shortest(grid: string[][], start: [number, number], goal: [number, number]): number {2  const rows = grid.length, cols = grid[0].length;3  const q: [number, number, number][] = [[start[0], start[1], 0]];4  const seen = new Set([start[0] * cols + start[1]]);5  for (let head = 0; head < q.length; head++) {6    const [r, c, d] = q[head];7    if (r === goal[0] && c === goal[1]) return d;8    for (const [nr, nc] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {9      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;10      if (grid[nr][nc] === "#" || seen.has(nr * cols + nc)) continue;11      seen.add(nr * cols + nc);12      q.push([nr, nc, d + 1]);13    }14  }15  return -1;16}
16 linesUTF-8TypeScript
  1. Queue of [row, col, distance]; a cell's key is row × cols + col.
  2. A head index turns the array into an O(1) queue; the first time we reach the goal is shortest.
  3. Enqueue valid neighbours and mark them visited immediately.

3.2Solution

Strict TypeScript, type-checked and tested.

Number of Islands

number-islands.tsTypeScript
1function numIslands(grid: string[][]): number {2  const rows = grid.length, cols = grid[0].length;3  const sink = (r0: number, c0: number) => {4    const stack: [number, number][] = [[r0, c0]];5    while (stack.length) {6      const [r, c] = stack.pop()!;7      if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== "1") continue;8      grid[r][c] = "0";9      stack.push([r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]);10    }11  };12  let count = 0;13  for (let r = 0; r < rows; r++) {14    for (let c = 0; c < cols; c++) {15      if (grid[r][c] === "1") {16        count++;17        sink(r, c);18      }19    }20  }21  return count;22}
22 linesUTF-8TypeScript

Step by step

  1. Scan the grid; unvisited land starts a new island.
  2. Sink the whole island with an explicit stack.
  3. Sunk cells are never counted again.

Complexity: O(rows × cols) time and space

Part 4 of 5

Q&A

What interviewers ask once your code works, and problems to try on your own.

4.1Interview questions

Answer out loud, then open.

BFS or DFS?
BFS for the fewest steps in an unweighted graph; DFS for connectivity, components and cycle detection. Both are O(V + E).
When do you mark a node as visited?
When you add it to the queue, not when you take it out; otherwise the same node is queued many times.
What if the edges have weights?
Use Dijkstra with a priority queue for non-negative weights, or 0-1 BFS with a deque when weights are only 0 or 1.

4.2Solo practice

Try these without looking; open the hint only when stuck.

EasyFlood Fill
Hint

DFS from the start pixel, change matching colours.

Part 5 of 5

Extra depth

More fully worked problems in the same family, and the mistakes that cost offers.

5.12 more worked problems

Each one: the problem, the plan, the code and its cost.

Show detailsHide details
Medium

Rotting Oranges

Each minute, rotten oranges rot their neighbours. How many minutes until none are fresh?

  1. Multi-source BFS: every rotten orange starts in the queue.
  2. Each BFS layer is one minute.
  3. If fresh oranges remain at the end, return −1.
rotting-oranges.tsTypeScript
1function orangesRotting(grid: number[][]): number {2  const rows = grid.length, cols = grid[0].length;3  let q: [number, number][] = [];4  let fresh = 0;5  for (let r = 0; r < rows; r++) {6    for (let c = 0; c < cols; c++) {7      if (grid[r][c] === 2) q.push([r, c]);8      else if (grid[r][c] === 1) fresh++;9    }10  }11  let minutes = 0;12  while (q.length && fresh > 0) {13    const next: [number, number][] = [];14    for (const [r, c] of q) {15      for (const [nr, nc] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {16        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] !== 1) continue;17        grid[nr][nc] = 2;18        fresh--;19        next.push([nr, nc]);20      }21    }22    q = next;23    minutes++;24  }25  return fresh === 0 ? minutes : -1;26}
26 linesUTF-8TypeScript

Complexity: O(rows × cols) time and space

Hard

Word Ladder

Shortest transformation from begin to end, changing one letter at a time through dictionary words.

  1. Words are nodes; one-letter differences are edges.
  2. Wildcard buckets (h*t) find neighbours without comparing every pair.
  3. BFS gives the shortest number of steps.
word-ladder.tsTypeScript
1function ladderLength(begin: string, end: string, words: string[]): number {2  if (!words.includes(end)) return 0;3  const buckets = new Map<string, string[]>();4  const pattern = (w: string, i: number) => w.slice(0, i) + "*" + w.slice(i + 1);5  for (const w of words) {6    for (let i = 0; i < w.length; i++) {7      const key = pattern(w, i);8      if (!buckets.has(key)) buckets.set(key, []);9      buckets.get(key)!.push(w);10    }11  }12  const q: [string, number][] = [[begin, 1]];13  const seen = new Set([begin]);14  for (let head = 0; head < q.length; head++) {15    const [word, steps] = q[head];16    if (word === end) return steps;17    for (let i = 0; i < word.length; i++) {18      for (const next of buckets.get(pattern(word, i)) ?? []) {19        if (seen.has(next)) continue;20        seen.add(next);21        q.push([next, steps + 1]);22      }23    }24  }25  return 0;26}
26 linesUTF-8TypeScript

Complexity: O(N · L²) time for N words of length L

5.2Traps

Bugs and misreadings that come up again and again with this pattern.

Show detailsHide details
  • Marking visited on pop instead of push (duplicates explode)
  • Recursion depth on big grids: use an explicit stack
AI Engineer · BFS and DFS