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.
Continue reading the full article on TildAlice
Top comments (0)