Adjacency List vs Matrix: 47% Faster DFS in Interview Code

Why Your Graph Choice Tanks Interview Performance

Most candidates freeze when asked “adjacency list or matrix?” during graph problems. They mumble something about sparse vs dense graphs, then pick one arbitrarily and hope it works. But here’s what actually matters: the wrong choice doesn’t just waste memory — it kills your runtime on test cases that matter.

I ran the same DFS traversal on a 1000-node graph using both representations. Adjacency list: 0.8ms. Adjacency matrix: 1.5ms. That’s 47% slower for identical logic.

And it gets worse with certain graph patterns.

The Memory Trap Nobody Mentions

Everyone knows the space complexity formulas. Adjacency list: $O(V + E)$ where $V$ is vertices and $E$ is edges. Adjacency matrix: $O(V^2)$ regardless of edge count.

But interview problems don’t care about your Big-O theory — they care about whether your code passes the hidden test case with 10,000 nodes and 15,000 edges (a fairly sparse social network graph). That adjacency matrix allocates 100 million boolean values. Python booleans are 1 byte each. You just consumed 95MB for a graph that should take under 1MB.

LeetCode’s memory limit? Often 256MB. You’re already using 37% of your budget before storing anything else.

The list representation for the same graph? 10,000 + 2 * 15,000 = 40,000 integers (edges stored twice for undirected graphs). At roughly 28 bytes per Python int object (due to Python’s object overhead—actual size varies by version and value), that’s approximately 1.1MB. 86x smaller.

But memory isn’t the only cost.

Iteration Speed: Where Matrices Silently Bleed Time

Here’s the code most candidates write for DFS with an adjacency matrix:

def dfs_matrix(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    n = len(graph)

    # This loop runs V times for EVERY node you visit
    for neighbor in range(n):
        if graph[start][neighbor] and neighbor not in visited:
            dfs_matrix(graph, neighbor, visited)

    return visited

See the problem? For every node, you scan ALL $V$ nodes to find neighbors. If the graph has 1000 nodes and average degree 3 (typical for interview problems), you’re checking 1000 cells to find 3 neighbors. That’s 997 wasted comparisons per node.

Total work: $O(V^2)$ just to traverse the graph, even though DFS should be $O(V + E)$.

Now the adjacency list version:

def dfs_list(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)

    # Only iterates over actual neighbors
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_list(graph, neighbor, visited)

    return visited

You only touch edges that exist. For a graph with $E$ edges, you do $O(E)$ work during traversal (plus $O(V)$ to visit each node once). On sparse graphs — which is most interview problems — $E \ll V^2$.

Let me show you the exact numbers.

Benchmark: Social Network Graph (Sparse)

import time
from collections import defaultdict
import random

# Build a sparse graph: 1000 nodes, average degree 5
n = 1000
avg_degree = 5
edges = set()

while len(edges) < n * avg_degree // 2:
    u = random.randint(0, n - 1)
    v = random.randint(0, n - 1)
    if u != v:
        edges.add((min(u, v), max(u, v)))

# Adjacency list representation
adj_list = defaultdict(list)
for u, v in edges:
    adj_list[u].append(v)
    adj_list[v].append(u)

# Adjacency matrix representation
adj_matrix = [[False] * n for _ in range(n)]
for u, v in edges:
    adj_matrix[u][v] = True
    adj_matrix[v][u] = True

# Time DFS with adjacency list
start_time = time.perf_counter()
visited_list = dfs_list(adj_list, 0)
list_time = (time.perf_counter() - start_time) * 1000

# Time DFS with adjacency matrix
start_time = time.perf_counter()
visited_matrix = dfs_matrix(adj_matrix, 0)
matrix_time = (time.perf_counter() - start_time) * 1000

print(f"Adjacency List: {list_time:.2f}ms")
print(f"Adjacency Matrix: {matrix_time:.2f}ms")
print(f"Speedup: {matrix_time / list_time:.1f}x")

Output on my M1 MacBook (Python 3.11):

Adjacency List: 0.83ms
Adjacency Matrix: 1.52ms
Speedup: 1.8x

The matrix version is 83% slower. And this is a connected component — we’re visiting every reachable node. If the interviewer asks “find all connected components,” you’ll traverse multiple times, multiplying the penalty.

When Matrices Actually Win

I’m not saying matrices are always wrong. There’s one scenario where they dominate: dense graphs with frequent edge lookups.

Checking if edge $(u, v)$ exists:
– Adjacency matrix: $O(1)$ — just graph[u][v]
– Adjacency list: $O(\text{degree}(u))$ — you scan the neighbor list

If you’re running Dijkstra’s algorithm or need to repeatedly check “is there an edge between these two nodes?” on a dense graph (where $E \approx V^2$, like a complete graph or near-complete), the matrix’s $O(1)$ edge lookup beats scanning a long neighbor list.

Example: graph coloring problems where you check conflicts between many node pairs. Or adjacency queries in a “friend recommendation” system where you need “are A and B friends?” constantly.

But here’s the thing — most interview graph problems are pathfinding (BFS/DFS), shortest path (Dijkstra, Bellman-Ford), or topology-based (topological sort, cycle detection). These iterate over neighbors, not query specific edges.

Edge Cases That Break Your Interview Solution

Disconnected Graphs

If the graph has multiple components, your DFS from node 0 might only visit 200 of 1000 nodes. The adjacency matrix still allocates $1000^2$ cells. The adjacency list only stores edges that exist. Wasted memory compounds.

Self-Loops and Multiple Edges

Some problems allow self-loops (node connected to itself) or multi-edges (multiple edges between the same pair). Adjacency matrices handle self-loops naturally (graph[i][i] = True) but can’t represent multiple edges without switching to an integer matrix (counting edges). Adjacency lists just append duplicates — though you might need to deduplicate depending on problem constraints.

Directed vs Undirected

For directed graphs, adjacency lists only store outgoing edges: adj_list[u].append(v) means $u \to v$. Matrices are symmetric for undirected graphs but asymmetric for directed. Both work, but debugging directed graphs with a matrix is harder — you have to remember row = source, column = destination.

Gotcha: Python List Initialization Trap

This is the bug that costs candidates 10 minutes during interviews:

# WRONG: all rows point to the same list object!
graph = [[False] * n] * n
graph[0][1] = True
# Now graph[1][1], graph[2][1], etc. are all True

The * n operator doesn’t deep-copy. You create one row, then replicate the reference $n$ times. Mutating any cell mutates all rows at that column index.

Correct initialization:

graph = [[False] * n for _ in range(n)]

Each row is a distinct list. I still see senior engineers trip on this under interview pressure.

Real Interview Problem Walkthrough: Course Schedule

LeetCode 207: Given numCourses and a list of prerequisite pairs [a, b] (must take b before a), determine if you can finish all courses (i.e., no cycles).

This is cycle detection in a directed graph. $V =$ numCourses, $E =$ len(prerequisites).

Typical constraints: $1 \leq V \leq 2000$, DOLLAR_AMOUNT_2 \leq E \leq 5000$.

Adjacency matrix: $2000^2 = 4{,}000{,}000$booleans = 4MB. Adjacency list: DOLLAR_AMOUNT_4 + 5000 = 7000$ entries ≈ 196KB (with Python overhead). 20x memory difference.

Runtime: DFS visits each node once and traverses each edge once. With adjacency list: $O(V + E) = 7000$ ops. With adjacency matrix: you scan $V$ columns for every node → $O(V^2) = 4{,}000{,}000$ ops. That’s 570x more work.

Here’s the solution using adjacency list:

from collections import defaultdict, deque

def canFinish(numCourses, prerequisites):
    # Build adjacency list
    graph = defaultdict(list)
    in_degree = [0] * numCourses

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1

    # Kahn's algorithm (topological sort via BFS)
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    count = 0

    while queue:
        node = queue.popleft()
        count += 1

        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return count == numCourses  # True if all nodes processed (no cycle)

Time complexity: $O(V + E)$. We build the graph in $O(E)$, initialize in-degrees in $O(V)$, then BFS processes each node once and each edge once.

Space complexity: $O(V + E)$ for the adjacency list + $O(V)$ for in-degree array + $O(V)$ for the queue.

If you used an adjacency matrix here, the test case with numCourses = 2000 would time out (or hit memory limits on some platforms). I’ve seen this exact mistake cost candidates the round.

The 3-Second Decision Rule

Here’s my heuristic when the interviewer finishes describing the problem:

1. Sparse graph (edges much less than $V^2$) + neighbor iteration (DFS, BFS, shortest path) → adjacency list
2. Dense graph (edges close to $V^2$) + frequent edge queries (“is there an edge between u and v?”) → adjacency matrix
3. Unsure → default to adjacency list (safer on memory, handles sparse gracefully, most interview graphs are sparse)

If the problem says “social network,” “prerequisites,” “dependencies,” “road network,” “web links” — it’s sparse. Real-world graphs rarely exceed $O(V \log V)$ edges.

If it says “complete graph,” “all pairs shortest path,” “graph coloring,” or explicitly mentions dense connectivity — consider the matrix.

Hybrid Approach: When You Need Both

Some problems require fast neighbor iteration and fast edge lookup. Example: “Clone Graph” (LeetCode 133) — you traverse neighbors but also need to check if you’ve already cloned a node.

Solution: adjacency list for iteration + hash set for visited checks. You’re not using a matrix, but you’re augmenting the list with a $O(1)$ lookup structure.

# Definition for a Node (provided by LeetCode)
# class Node:
#     def __init__(self, val=0, neighbors=None):
#         self.val = val
#         self.neighbors = neighbors if neighbors is not None else []

def cloneGraph(node):
    if not node:
        return None

    clones = {}  # Original node -> cloned node mapping

    def dfs(original):
        if original in clones:
            return clones[original]

        clone = Node(original.val)
        clones[original] = clone  # Mark as cloned before recursion

        for neighbor in original.neighbors:
            clone.neighbors.append(dfs(neighbor))

        return clone

    return dfs(node)

Here clones acts like an edge-existence check (have we seen this node?) but doesn’t replace the neighbor iteration — we still use original.neighbors (implicit adjacency list).

What the Textbooks Don’t Tell You

Most algorithm books present adjacency list and matrix as equivalent choices differing only in constant factors. That’s technically true for worst-case Big-O. But constant factors matter in interviews:

• Python’s list append is amortized $O(1)$, but reallocation can cause 10-50ms spikes on large graphs. Preallocating list size helps: graph = [[] for _ in range(n)]
• Dictionary-based adjacency lists (defaultdict(list)) are slower than array-indexed lists if nodes are integers 0..n-1. Use arrays when possible.
• Adjacency matrices in NumPy (np.zeros((n, n), dtype=bool)) are faster than Python lists of lists (contiguous memory, vectorized ops), but LeetCode often doesn’t allow NumPy imports.

I’m not entirely sure why some online judges restrict NumPy — maybe to level the playing field, maybe because of import overhead. Either way, assume pure Python.

FAQ

Q: Can I convert between adjacency list and matrix during the interview?

Yes, but it costs you time. Converting list → matrix requires $O(V^2)$ to initialize the matrix, then $O(E)$ to populate edges. Converting matrix → list is $O(V^2)$ (scan entire matrix). If you realize mid-solution you chose wrong, it’s usually faster to restart with the right representation than to convert.

Q: What if the graph nodes aren’t integers 0..n-1?

Use a dictionary-based adjacency list: graph = defaultdict(list), where keys are node identifiers (strings, tuples, whatever). You lose array indexing speed, but it’s still $O(1)$ average-case lookup. Adjacency matrices require contiguous integer indices, so you’d need to map arbitrary IDs → indices first (extra bookkeeping).

Q: Does adjacency list order matter for DFS/BFS correctness?

No for correctness (you’ll visit all reachable nodes either way), but yes for output order if the problem asks for a specific traversal sequence. If the problem says “return nodes in lexicographical order,” you’ll need to sort neighbor lists — which adjacency lists make easy (graph[u].sort()). Matrices would require scanning and sorting indices.

When I’d Actually Pick a Matrix

Despite everything I’ve said, I’ve used matrices in production code for one specific case: precomputed distance tables. If you run Floyd-Warshall to compute all-pairs shortest paths ($O(V^3)$), the output is naturally a $V \times V$ matrix where dist[i][j] = shortest path from $i$ to $j$.

You wouldn’t build the input graph as a matrix (you’d still use an adjacency list for the algorithm), but the result is a matrix because every pair has a distance. Trying to store that in a dictionary of dictionaries is just a slower matrix.

Same for adjacency in extremely dense graphs — if you’re working with a clique (everyone connected to everyone), the matrix is honest about the structure.

But in interviews? I’d estimate 95% of graph problems favor adjacency lists. The remaining 5% either explicitly say “dense graph” or involve matrix-specific operations (like “number of islands” grid problems, which are technically matrices but not graph representations in the traditional sense).

The Verdict

Default to adjacency lists for interviews unless you have a specific reason to use a matrix. They’re faster on sparse graphs (which is almost all interview graphs), use less memory, and match the iteration patterns of BFS, DFS, Dijkstra, and topological sort.

If you need $O(1)$ edge existence checks, add a hash set or dictionary alongside the list. If the graph is genuinely dense and you’re doing all-pairs operations, then — and only then — reach for the matrix.

And when you’re practicing these problems at midnight, remember: the representation choice happens in the first 30 seconds of coding. Get it wrong, and you’re rewriting the whole solution. Get it right, and the rest of the problem writes itself.