L27 · Graphs I — Representation & DFS

Series: LeetCode — From Basics to Interview-Ready · Session 27 / 65 · Phase 1 · Core patterns

Why this session exists

Grids are graphs. That single sentence collapses an entire category of problems that otherwise look like a separate topic. A 2D board of land and water is a graph where every cell is a node and every orthogonally adjacent land pair is an edge. Once you internalise that, "Number of Islands" stops being a grid puzzle and becomes "count connected components", which you already know how to do.

The reason people struggle with graph problems is not the traversal. DFS is six lines. The struggle is representation: given a problem statement that mentions courses, or friends, or cities, or a matrix, what is the node and what is the edge? Answer that correctly and the rest of the session is typing. Answer it wrong and no amount of algorithmic cleverness saves you.

This session is deliberately narrow. One representation (adjacency list), one traversal (DFS), one bookkeeping structure (visited set). Sessions 28 through 30 add BFS, topological order and union-find on top of exactly this foundation, so getting the base solid now pays four times.

Blank-file warm-up

Five minutes, empty file, no notes. Write from memory:

adj = defaultdict(list)   — build it from an edge list
dfs(node)                 — recursive, with a visited set

Specifically: given edges = [[0,1],[1,2],[3,4]] and n = 5, build the adjacency list for an undirected graph, then write a DFS that visits every node reachable from 0 and prints them.

The two things that go wrong from memory: forgetting that undirected means you append the edge in both directions, and marking a node visited at the wrong moment. If either of those wobbles, that is today's finding.

Pattern anatomy

The shape of problem that summons this pattern: things connected to other things, and a question about reachability or grouping. Not ordering (that is session 29), not shortest distance (that is session 28) — just "what can I reach" or "how many separate clumps are there".

The invariant DFS maintains is exactly one sentence: every node in visited has already had its own expansion started, so it never needs to be expanded again. That is what makes the traversal terminate on cyclic graphs. Drop the invariant and a triangle graph loops forever.

The adjacency list, built from an edge list:

from collections import defaultdict
 
def build(n, edges, directed=False):
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        if not directed:
            adj[v].append(u)
    return adj

The DFS template. Learn this exact shape:

def dfs(node, adj, visited):
    visited.add(node)              # mark on ENTRY, not on exit
    for nxt in adj[node]:
        if nxt not in visited:
            dfs(nxt, adj, visited)

Counting connected components is then a single sweep over all nodes:

def count_components(n, edges):
    adj = build(n, edges)
    visited = set()
    count = 0
    for node in range(n):
        if node not in visited:
            dfs(node, adj, visited)
            count += 1             # each fresh start = one new component
    return count

And the grid variant, where the adjacency list is implicit — you never build it, you compute neighbours on the fly:

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
 
def grid_dfs(grid, r, c, seen):
    R, C = len(grid), len(grid[0])
    seen.add((r, c))
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < R and 0 <= nc < C and (nr, nc) not in seen and grid[nr][nc] == "1":
            grid_dfs(grid, nr, nc, seen)

That bounds check — 0 <= nr < R and 0 <= nc < C — must come before the grid lookup in the same and chain. Python short-circuits left to right, so ordering it correctly is what prevents an index error rather than an explicit try block.

The cue

You are looking at a graph-DFS problem when the statement contains one of these tells:

1. A 2D grid plus a notion of adjacency. Islands, regions, provinces, flood fill, surrounded areas, rotting fruit. The word "adjacent" or "connected horizontally or vertically" is the giveaway. Cells are nodes; the four (or eight) directions are edges.
2. "How many groups / islands / provinces / friend circles" — that is literally counting connected components. Outer loop over all nodes, inner DFS, increment on each fresh start.
3. An explicit edge list or n nodes numbered 0 to n−1. LeetCode hands you edges = [[a,b],...]. Build the adjacency list immediately, before you think about anything else.
4. "Can you reach X from Y" / "is everything connected". Pure reachability. Run one DFS from a source and compare len(visited) against n.
5. A structure with pointers and possible cycles — Clone Graph, copying a linked structure. The visited map does double duty: cycle guard and old-node-to-new-node mapping.

The negative cue matters too. If the problem asks for the shortest path in an unweighted graph, DFS is the wrong tool — use BFS (session 28). DFS finds a path, not the shortest one. If it asks for an order respecting dependencies, that is topological sort (session 29).

Guided solve

Number of Islands. Given an m × n grid of "1" (land) and "0" (water), count the number of islands, where an island is land connected horizontally or vertically.

Start by naming the graph out loud, because this is the step interviewers are actually grading. Nodes: every cell containing "1". Edges: between orthogonally adjacent land cells. Question: number of connected components. That translation is the whole problem — everything after it is the template you already wrote.

The algorithm: sweep every cell. When you find an unvisited "1", you have discovered a new island, so increment the counter and then run a DFS that consumes the entire island so you never count any of its cells again.

def numIslands(grid):
    if not grid:
        return 0
    R, C = len(grid), len(grid[0])
    count = 0
 
    def sink(r, c):
        if r < 0 or r >= R or c < 0 or c >= C or grid[r][c] != "1":
            return
        grid[r][c] = "0"                 # mark visited by mutating the grid
        sink(r + 1, c)
        sink(r - 1, c)
        sink(r, c + 1)
        sink(r, c - 1)
 
    for r in range(R):
        for c in range(C):
            if grid[r][c] == "1":
                count += 1
                sink(r, c)
    return count

Two decisions worth defending aloud.

Mutating the grid instead of keeping a visited set. Setting land to water as you go is O(1) extra space instead of O(m·n) for a set of coordinates. The cost is that you destroy the caller's input. In an interview, say this explicitly: "I'm sinking the island in place for constant extra space — if the input must be preserved I'd use a visited set instead, same complexity in time." Naming the tradeoff is worth more than either choice.

Guard-at-the-top recursion instead of guard-before-the-call. Both work. Guarding inside sink means one bounds check written once, at the cost of some no-op recursive calls. Guarding before each call avoids those frames but repeats the condition four times. I prefer the top guard because it is shorter and there is exactly one place for a bounds bug to live.

Trace it mentally on a single-row grid ["1","1","0","1"]. The sweep hits (0,0), counts island 1, sinks (0,0) and (0,1). It skips (0,2) which is water. It hits (0,3), counts island 2, sinks it. Answer 2. Correct.

Solo timed

Fifteen minutes each, timer visible, no editorial until it fires.

• Clone Graph — the visited structure is a dict, not a set, and it maps original node to its clone. Create the clone before you recurse into neighbours, or a cycle sends you into infinite recursion.
• Max Area of Island — same sweep as Number of Islands, but the DFS returns a number instead of nothing. Think about what the base case should return and what you accumulate from the four recursive calls.

If both land early, do Flood Fill as a third. It is the same template with a colour comparison instead of a land check, and the one edge case is what happens when the new colour equals the starting colour.

Common failure modes

Marking visited on exit instead of on entry. If you add the node to visited after the neighbour loop, a cycle re-enters the node before the mark lands and you recurse forever. Mark first line of the function, always.

Forgetting the reverse edge in an undirected graph. adj[u].append(v) without adj[v].append(u) silently makes the graph directed. Traversal still runs and still returns an answer — just the wrong one. This is the most expensive one-line bug in graph problems because there is no crash to point at it.

Bounds check ordering in grids. Writing if grid[nr][nc] == "1" and 0 <= nr < R throws before the guard runs. Negative indices are worse: grid[-1][0] is a valid Python expression that silently reads the last row, so you get wrong answers with no exception at all.

Counting components inside the DFS instead of outside. The increment belongs in the outer sweep, once per fresh start. Incrementing per visited node counts cells, not islands.

Using a plain dict where defaultdict(list) was intended. adj[u].append(v) raises KeyError on a node with no prior entry. Isolated nodes are a real test case.

Complexity

Time: O(V + E). Every node is added to visited exactly once, and once marked it is never expanded again. Each edge is examined once from each endpoint in an undirected graph, so 2E edge inspections total, which is O(E). For a grid, V = m·n and E is at most 4·m·n (each cell has at most four neighbours), so the whole thing collapses to O(m·n) — linear in the number of cells, which is the best possible since you must at least read every cell to know whether it is land.

Space: O(V). The visited set holds up to V entries. The recursion stack adds up to O(V) in the worst case — a snake-shaped island of m·n cells produces a chain of m·n frames. If you sink the grid in place you drop the set but keep the stack, so worst-case space stays O(V); the win is a constant factor, not an asymptotic one.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Number of Islands enters the queue at whatever status today's attempt earned. If the blank-file adjacency list came out directed when it should have been undirected, log the warm-up itself as failed — the queue tracks retrieval from cold memory, not eventual correctness after a hint.