BFS and DFS on Graphs and Grids — The Complete Interview Guide

Problem Statement#

This guide is the foundation for every grid and graph traversal problem in the LeetCode 75, Blind 75, and NeetCode 150 lists. We will cover the patterns, not just one problem.

Core questions a graph traversal answers:

• How many connected components exist?
• What is the shortest number of steps from A to B?
• Which cells are reachable from a given source?
• How do regions spread over time (multi-source BFS)?

Constraints we typically see:

• Grids of size up to 1000 x 1000
• Graphs with V up to 10^5 and E up to 2 * 10^5
• Time budget around 1 to 2 seconds

Input:  grid = [[1,1,0],[0,1,0],[0,0,1]]
Output: numberOfIslands = 2

Why This Problem Matters#

If you only had time to master one topic for a FAANG coding interview, BFS and DFS on grids would be the highest leverage choice. Keywords: "BFS interview pattern", "DFS FAANG", "graph traversal Python", "grid traversal JavaScript". Amazon, Google, Meta, and Microsoft pull from this template constantly.

A 2-D grid is simply a graph where each cell has up to four neighbours. Once you internalise that, "Number of Islands", "Flood Fill", "Walls and Gates", "Rotting Oranges", and "Word Ladder" all collapse into the same skeleton.

The Core Insight#

Every grid traversal answers one of two questions: "is this reachable" (DFS or BFS) or "what is the shortest distance" (BFS only). DFS uses a stack (often the call stack via recursion); BFS uses a queue. Mark visited cells the moment you push them, never when you pop them, otherwise you double-enqueue and timeout.

Visual Dry Run#

Walking BFS over a 3x3 grid starting at (0,0) with land cells marked 1.

Solution (Optimal)#

Pattern 1 — DFS flood fill (mark in place)#

class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0
        rows, cols = len(grid), len(grid[0])
        count = 0
 
        def dfs(r, c):
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return
            if grid[r][c] != '1':
                return
            grid[r][c] = '0'
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)
 
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    count += 1
                    dfs(r, c)
        return count

var numIslands = function(grid) {
    if (!grid || grid.length === 0) return 0;
    const rows = grid.length, cols = grid[0].length;
    let count = 0;
 
    const dfs = (r, c) => {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return;
        if (grid[r][c] !== '1') return;
        grid[r][c] = '0';
        dfs(r + 1, c); dfs(r - 1, c);
        dfs(r, c + 1); dfs(r, c - 1);
    };
 
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === '1') {
                count++;
                dfs(r, c);
            }
        }
    }
    return count;
};

Pattern 2 — BFS shortest path on unweighted graph#

from collections import deque
 
def shortest_path(grid, start, end):
    rows, cols = len(grid), len(grid[0])
    q = deque([(start[0], start[1], 0)])
    seen = {start}
    while q:
        r, c, d = q.popleft()
        if (r, c) == end:
            return d
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            nr, nc = r+dr, c+dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0 and (nr,nc) not in seen:
                seen.add((nr,nc))
                q.append((nr,nc,d+1))
    return -1

Pattern 3 — Multi-source BFS (rotting oranges, walls and gates)#

Push every source at distance 0, then expand layer by layer. The first time you reach a target gives its minimum distance to ANY source.

Pattern 4 — Connected components on adjacency list#

def count_components(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    seen = [False] * n
    count = 0
    for i in range(n):
        if not seen[i]:
            count += 1
            stack = [i]
            while stack:
                node = stack.pop()
                if seen[node]:
                    continue
                seen[node] = True
                for nb in graph[node]:
                    if not seen[nb]:
                        stack.append(nb)
    return count

Pattern 5 — Cycle detection in directed graph (3-colour DFS)#

Pattern 6 — Topological sort (Kahn's BFS)#

Pattern 7 — 0-1 BFS for weighted shortest path with weights 0 and 1#

Time: O(V + E) for both BFS and DFS — every vertex and edge visited exactly once. Space: O(V) — the queue, stack, or visited set.

Common Mistakes#

• Marking visited only when popping (causes duplicate enqueues and TLE).
• Using DFS for shortest path on unweighted graphs (BFS is required).
• Forgetting to check bounds before checking the cell value (out-of-range index error).
• Mutating the input grid when the interviewer expects it preserved.
• Recursing too deep on a 1000x1000 grid (Python hits the 1000-frame limit; switch to iterative or raise the limit).

Interview Tips#

• Always restate whether the graph is directed, weighted, and whether self-loops or duplicate edges are allowed.
• Ask if you can mutate the input grid; many interviewers prefer an explicit visited set.
• For shortest path, default to BFS; only reach for Dijkstra when weights vary.
• Mention the V plus E complexity out loud, not just O(N).
• Sketch the queue or stack on paper for the first three iterations.

Follow-up Questions#

• What if diagonals count as connected? (Switch to 8 directions.)
• What if the grid is too big to fit in memory? (Stream rows; track only the previous row's component IDs.)
• What about weighted edges? (Dijkstra or 0-1 BFS.)
• Detect a cycle in an undirected graph during DFS? (Track parent and check for back edges.)
• Convert recursion to iteration to avoid stack overflow on 10^6 nodes.

Key Takeaways#

• A 2-D grid is just a graph with up to four edges per cell.
• BFS gives shortest path on unweighted graphs; DFS does not.
• Mark visited at enqueue time, not dequeue time.
• Multi-source BFS handles "spread from many origins" in one pass.
• Both BFS and DFS run in O(V + E) time and O(V) space.
• Topological sort, cycle detection, and connected components are DFS or BFS variants.
• Master these seven patterns and 90 percent of graph interview problems become trivial.