BFS and DFS pattern

Explore grids and graphs; BFS gives shortest steps.

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

TypeScriptKotlinJava
bfs-shortest-steps.tsTypeScriptCopy
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
bfs-shortest-steps.ktKotlinCopy
1fun shortest(grid: Array<CharArray>, start: Pair<Int, Int>, goal: Pair<Int, Int>): Int {2    val rows = grid.size3    val cols = grid[0].size4    val q = java.util.ArrayDeque<IntArray>()5    q.add(intArrayOf(start.first, start.second, 0))6    val seen = Array(rows) { BooleanArray(cols) }7    seen[start.first][start.second] = true8    val dirs = arrayOf(intArrayOf(1, 0), intArrayOf(-1, 0), intArrayOf(0, 1), intArrayOf(0, -1))9    while (q.isNotEmpty()) {10        val (r, c, d) = q.poll()11        if (r == goal.first && c == goal.second) return d12        for ((dr, dc) in dirs) {13            val nr = r + dr14            val nc = c + dc15            if (nr !in 0 until rows || nc !in 0 until cols) continue16            if (grid[nr][nc] == '#' || seen[nr][nc]) continue17            seen[nr][nc] = true18            q.add(intArrayOf(nr, nc, d + 1))19        }20    }21    return -122}
22 linesUTF-8Kotlin
bfs-shortest-steps.javaJavaCopy
1static int shortest(char[][] grid, int[] start, int[] goal) {2  int rows = grid.length, cols = grid[0].length;3  Deque<int[]> q = new ArrayDeque<>();4  q.add(new int[] {start[0], start[1], 0});5  boolean[][] seen = new boolean[rows][cols];6  seen[start[0]][start[1]] = true;7  int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};8  while (!q.isEmpty()) {9    int[] cur = q.poll();10    if (cur[0] == goal[0] && cur[1] == goal[1]) return cur[2];11    for (int[] d : dirs) {12      int nr = cur[0] + d[0], nc = cur[1] + d[1];13      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;14      if (grid[nr][nc] == '#' || seen[nr][nc]) continue;15      seen[nr][nc] = true;16      q.add(new int[] {nr, nc, cur[2] + 1});17    }18  }19  return -1;20}
20 linesUTF-8Java
  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

TypeScriptKotlinJava
number-islands.tsTypeScriptCopy
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
number-islands.ktKotlinCopy
1fun numIslands(grid: Array<CharArray>): Int {2    val rows = grid.size3    val cols = grid[0].size4    fun sink(r0: Int, c0: Int) {5        val stack = ArrayDeque<IntArray>()6        stack.addLast(intArrayOf(r0, c0))7        while (stack.isNotEmpty()) {8            val (r, c) = stack.removeLast()9            if (r !in 0 until rows || c !in 0 until cols || grid[r][c] != '1') continue10            grid[r][c] = '0'11            stack.addLast(intArrayOf(r + 1, c))12            stack.addLast(intArrayOf(r - 1, c))13            stack.addLast(intArrayOf(r, c + 1))14            stack.addLast(intArrayOf(r, c - 1))15        }16    }17    var count = 018    for (r in 0 until rows) {19        for (c in 0 until cols) {20            if (grid[r][c] == '1') {21                count++22                sink(r, c)23            }24        }25    }26    return count27}
27 linesUTF-8Kotlin
number-islands.javaJavaCopy
1static int numIslands(char[][] grid) {2  int rows = grid.length, cols = grid[0].length, count = 0;3  for (int r = 0; r < rows; r++) {4    for (int c = 0; c < cols; c++) {5      if (grid[r][c] == '1') {6        count++;7        sink(grid, r, c);8      }9    }10  }11  return count;12}13 14static void sink(char[][] grid, int r0, int c0) {15  Deque<int[]> stack = new ArrayDeque<>();16  stack.push(new int[] {r0, c0});17  while (!stack.isEmpty()) {18    int[] cur = stack.pop();19    int r = cur[0], c = cur[1];20    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != '1') continue;21    grid[r][c] = '0';22    stack.push(new int[] {r + 1, c});23    stack.push(new int[] {r - 1, c});24    stack.push(new int[] {r, c + 1});25    stack.push(new int[] {r, c - 1});26  }27}
27 linesUTF-8Java

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.tsTypeScriptCopy
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.tsTypeScriptCopy
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