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.
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.
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.
Count groups of connected '1' cells in a grid.
Plan before you code
- Scan every cell.
- On an unvisited land cell, count an island and flood-fill it.
- Flood-fill sinks cells so they are not counted again.
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
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}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}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}- Queue of [row, col, distance]; a cell's key is row × cols + col.
- A head index turns the array into an O(1) queue; the first time we reach the goal is shortest.
- Enqueue valid neighbours and mark them visited immediately.
3.2Solution
Strict TypeScript, type-checked and tested.
Number of Islands
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}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}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}Step by step
- Scan the grid; unvisited land starts a new island.
- Sink the whole island with an explicit stack.
- Sunk cells are never counted again.
Complexity: O(rows × cols) time and space
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?
When do you mark a node as visited?
What if the edges have weights?
4.2Solo practice
Try these without looking; open the hint only when stuck.
Hint
DFS from the start pixel, change matching colours.
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
Rotting Oranges
Each minute, rotten oranges rot their neighbours. How many minutes until none are fresh?
- Multi-source BFS: every rotten orange starts in the queue.
- Each BFS layer is one minute.
- If fresh oranges remain at the end, return −1.
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}Complexity: O(rows × cols) time and space
Word Ladder
Shortest transformation from begin to end, changing one letter at a time through dictionary words.
- Words are nodes; one-letter differences are edges.
- Wildcard buckets (h*t) find neighbours without comparing every pair.
- BFS gives the shortest number of steps.
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}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