L27 · Graphs I — Representation & DFS

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

Watch first

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.

Worked variant — Clone Graph, where visited stops being a set

Island counting hides something important: the visited set is doing two jobs at once, and only one of them survives into harder problems. Clone Graph separates them.

def clone_graph(node):
    """Deep-copy an undirected connected graph. LC 133."""
    if not node:
        return None
 
    # The 'visited' structure is a MAP, not a set: original -> clone.
    # It answers 'have I seen this?' AND 'what did I build for it?'.
    # A set answers only the first, which is why a set cannot work here.
    old_to_new = {}
 
    def dfs(cur):
        if cur in old_to_new:
            return old_to_new[cur]     # already cloned; return the SAME object
 
        copy = Node(cur.val)
        old_to_new[cur] = copy         # register BEFORE recursing.
                                       # Do it after and a cycle re-enters
                                       # this node, finds nothing, and
                                       # recurses forever.
 
        for nei in cur.neighbors:
            copy.neighbors.append(dfs(nei))
        return copy
 
    return dfs(node)

Two things to extract and carry forward.

Register before you recurse. This is the general form of "mark visited on entry, not on exit". In island counting you sink the cell to '0' the moment you arrive; here you insert into the map the moment you create the clone. Both are the same rule, and violating it produces infinite recursion on any cyclic input while still passing acyclic tests.

Visited is whatever answers "have I processed this node, and what did I conclude?" A set is the degenerate case where the conclusion is nothing. When the conclusion is a value — a clone, a colour, a component id, a memoised cost — the same slot becomes a dict. Recognising that the set is a special case of the dict is what makes graph memoisation feel like the same pattern rather than a new one, and it is exactly the bridge into the DP module.

The complexity is unchanged: O(V + E), because each node is cloned once and each edge is walked once from each endpoint.

Memory hook — "nodes, edges, mark on entry"

Three beats, in order, and the order matters because it is the order you should think in when a graph problem appears:

• Nodes — name the node out loud before writing anything. A course. A cell (r, c). A word in the dictionary. A state (position, keys_held). If you cannot say what one node is in a short phrase, you have not modelled the problem yet, and any code you write is guessing.
• Edges — name the relation and its direction. "Prerequisite points to dependent." "Cell to its four orthogonal neighbours." Direction is the detail people skip; undirected means you insert into both adjacency lists, and forgetting the second insert produces a graph that is quietly half missing.
• Mark on entry — add to visited when you arrive, never when you leave. On entry the mark blocks re-entry and terminates cycles. On exit it does nothing until it is too late.

For the grid case the sub-peg is "in bounds, is land, not seen" — the three guards of every grid DFS, in that order. Order matters: bounds must be checked before you index, or you get an IndexError from the very guard meant to prevent it. Python's negative indexing makes r == -1 silently wrap to the last row instead of failing loudly, which is why the bounds check must be explicit rather than relying on an exception.

What interviewers actually ask

Graph representation is the highest-leverage topic in the whole rotation, because the traversal is short and the modelling is where candidates separate.

• 200 · Number of Islands (Medium) — Amazon, Google, Meta, Microsoft, Bloomberg. Probing whether you see the grid as a graph. Follow-up: "the grid is too large for the recursion depth" — convert to an explicit stack, or use BFS.
• 133 · Clone Graph (Medium) — Meta, Amazon, Google. Probing the visited-as-map insight above. Follow-up: "what if the graph is disconnected?" — you need an outer loop over all nodes.
• 695 · Max Area of Island (Medium) — Amazon, Google. Probing whether your DFS can return a value rather than only mutate. Follow-up: return the shape rather than the size, which is 694.
• 547 · Number of Provinces (Medium) — Amazon, Bloomberg. Probing adjacency matrix input rather than an edge list — same algorithm, different neighbour lookup.
• 417 · Pacific Atlantic Water Flow (Medium) — Google, Amazon. Probing the reversal trick: do not simulate flow from every cell, run DFS inward from each ocean's border and intersect.
• 130 · Surrounded Regions (Medium) — Amazon, Google. Probing the same inversion — mark what touches the border as safe, flip the rest.
• 207 · Course Schedule (Medium) — Amazon, Meta, Google, Uber. Probing cycle detection in a directed graph, where a single visited set is insufficient and you need three states. That is L29, but it is the follow-up they reach for from here.

The escalation to watch: "is there a cycle?" on a directed graph. The undirected trick of skipping the parent does not transfer, and answering as if it does is the most common way this topic goes wrong.

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.