Stage 1 · Code

Graphs & Backtracking

Graph Representations & Traversals

Master adjacency lists, DFS, and BFS — the three tools that unlock 80% of graph interview problems.

12 min readLeetCode Patterns for InterviewsCode

Adjacency List vs Adjacency Matrix

A graph is a collection of nodes (vertices) and edges connecting them. Two common ways to store a graph in code:

Property	Adjacency List	Adjacency Matrix
Storage	O(V + E)	O(V²)
Edge lookup	O(degree) ≈ O(V) worst	O(1)
Iterate neighbors	O(degree) ≈ fast	O(V) — must scan full row
Weighted edges	Store pair (neighbor, weight)	Store weight in cell
Common in interviews	Almost always	Rare — dense graphs only

For nearly every LeetCode graph problem, an adjacency list is the right choice. It is sparse-friendly and iterating neighbors is fast.

Goadjacency-list-templates.go

19 linesLn 1, Col 1Go

Choose the representation that matches the problem: map[int][]int for general graphs, a 2D grid with direction arrays for matrix-based graphs like Number of Islands.

Graph: 0 → 1 → 2 → 3, 2 → 0 (directed cycle)

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. Implemented recursively (implicit call stack) or iteratively (explicit stack). Critical for connectivity, cycle detection, and topological ordering.

Godfs-—-recursive-adjacency-list.go

21 linesLn 1, Col 1Go

DFS visits node 0 → neighbors {1, 2}, visits 1 → neighbor {2}, visits 2 → neighbors {0 (visited), 3}, visits 3. Output: 0, 1, 2, 3.

For grid-based problems (Number of Islands), DFS on a 2D matrix is the go-to pattern. Each cell is a node; directional neighbors are edges.

Godfs-—-grid-(flood-fill-pattern).go

25 linesLn 1, Col 1Go

Sink-and-count pattern: when we find '1', increment count and DFS to sink the entire connected component. Runtime O(rows × cols), space O(rows × cols) worst-case call stack.

Breadth-First Search (BFS)

BFS explores nodes level by level using a queue. It guarantees the shortest path in unweighted graphs and is the right tool for spreading processes (rotten oranges, infection, word ladder).

Gobfs-—-iterative-adjacency-list.go

17 linesLn 1, Col 1Go

Mark visited as soon as we enqueue (not when we dequeue) to avoid duplicate enqueues. BFS visits in order of distance from start.

BFS levels from node 0

DFS vs BFS

Criterion	DFS	BFS
Data structure	Stack (recursive or explicit)	Queue
Shortest path in unweighted graph	No — finds any path	Yes — guaranteed shortest
Space complexity	O(h) where h = depth	O(w) where w = max width (often larger)
Cycle detection	Yes — back edge in recursion	Less natural
Topological sort	Yes — post-order DFS	Yes — Kahn's algorithm
Connected components	Natural fit	Also works

Choose based on what you need

Need shortest path in an unweighted graph? Use BFS. Need to exhaust all possibilities or detect cycles? Use DFS. Both can count connected components and detect bipartiteness, but BFS feels more natural for 'levels' while DFS feels natural for 'paths'.

When to Use

Adjacency list for almost all problems — sparse graphs with up to 10⁵ nodes.
DFS when you need to explore all paths, detect cycles, or perform flood fill.
BFS when the graph is unweighted and you need the shortest number of edges.
Grid as graph when the input is a 2D matrix (grid[r][c] = node, 4-dir moves = edges).
Clone graph / deep copy: DFS with a cache of cloned nodes (node → clone).

Problems

#200Number of IslandsMediumGrid DFS / BFS · O(m × n) time · O(m × n) space #133Clone GraphMediumDFS with hash map cache · O(V + E) time · O(V) space #695Max Area of IslandMediumGrid DFS with area tracking · O(m × n) time · O(m × n) space

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.