Use adjacency lists for interviews: build in O(V + E), traverse in O(V + E). For grids, each cell is a node and each valid direction is an edge.
| operation | Python | Go | TypeScript | C++ |
|---|
directed
O(V + E) |
g = [[] for _ in range(n)]
for u, v in edges:
g[u].append(v) |
g := make([][]int, n)
for _, e := range edges {
u, v := e[0], e[1]
g[u] = append(g[u], v)
} |
const g = Array.from({ length: n }, () => [] as number[])
for (const [u, v] of edges) g[u].push(v) |
vector<vector<int>> g(n);
for (auto [u, v] : edges) g[u].push_back(v); |
undirected
O(V + E) |
g = [[] for _ in range(n)]
for u, v in edges:
g[u].append(v)
g[v].append(u) |
g[u] = append(g[u], v)
g[v] = append(g[v], u) |
g[u].push(v)
g[v].push(u) |
g[u].push_back(v);
g[v].push_back(u); |
weighted
O(V + E) |
g = [[] for _ in range(n)]
for u, v, w in edges:
g[u].append((v, w)) |
type Edge struct { to, w int }
g := make([][]Edge, n)
g[u] = append(g[u], Edge{v, w}) |
type Edge = [to: number, w: number]
const g: Edge[][] = Array.from({ length: n }, () => [])
g[u].push([v, w]) |
vector<vector<pair<int, int>>> g(n);
g[u].push_back({v, w}); |
| operation | Python | Go | TypeScript | C++ |
|---|
iterative DFS
O(V + E) |
def dfs(g, start):
order, seen = [], {start}
st = [start]
while st:
u = st.pop()
order.append(u)
for v in g[u]:
if v not in seen:
seen.add(v); st.append(v)
return order |
seen := map[int]struct{}{s: {}}
st := []int{s}
for len(st) > 0 {
u := st[len(st)-1]; st = st[:len(st)-1]
for _, v := range g[u] { if _, ok := seen[v]; !ok { seen[v] = struct{}{}; st = append(st, v) } }
} |
const seen = new Set<number>([s])
const st = [s]
while (st.length) {
const u = st.pop()!
for (const v of g[u]) if (!seen.has(v)) { seen.add(v); st.push(v) }
} |
vector<char> seen(n);
vector<int> st{s}; seen[s] = 1;
while (!st.empty()) {
int u = st.back(); st.pop_back();
for (int v : g[u]) if (!seen[v]) { seen[v] = 1; st.push_back(v); }
} |
BFS shortest path
unweighted
O(V + E) |
from collections import deque
def bfs_dist(g, start):
dist = {start: 0}
q = deque([start])
while q:
u = q.popleft()
for v in g[u]:
if v not in dist:
dist[v] = dist[u] + 1
q.append(v)
return dist |
dist := map[int]int{s: 0}
q, head := []int{s}, 0
for head < len(q) {
u := q[head]; head++
for _, v := range g[u] { if _, ok := dist[v]; !ok { dist[v] = dist[u] + 1; q = append(q, v) } }
} |
const dist = new Map<number, number>([[s, 0]])
const q = [s]; let head = 0
while (head < q.length) {
const u = q[head++]
for (const v of g[u]) if (!dist.has(v)) { dist.set(v, dist.get(u)! + 1); q.push(v) }
} |
vector<int> dist(n, -1);
queue<int> q; dist[s] = 0; q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u]) if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
} |
Kahn topo sort
DAG only
O(V + E) |
from collections import deque
def topo(n, edges):
g = [[] for _ in range(n)]
indeg = [0] * n
for u, v in edges:
g[u].append(v); indeg[v] += 1
q = deque(i for i, d in enumerate(indeg) if d == 0)
order = []
while q:
u = q.popleft(); order.append(u)
for v in g[u]:
indeg[v] -= 1
if indeg[v] == 0: q.append(v)
return order if len(order) == n else [] |
indeg := make([]int, n)
// build g and indeg[v]++ for each u->v
q, head := []int{}, 0
// enqueue all indeg 0
for head < len(q) {
u := q[head]; head++
for _, v := range g[u] { indeg[v]--; if indeg[v] == 0 { q = append(q, v) } }
} |
const indeg = Array(n).fill(0)
// build g and indeg[v]++
const q: number[] = [], order: number[] = []
let head = 0
while (head < q.length) {
const u = q[head++]; order.push(u)
for (const v of g[u]) if (--indeg[v] === 0) q.push(v)
} |
vector<int> indeg(n), order;
queue<int> q;
// build g and indeg[v]++; push zeros
while (!q.empty()) {
int u = q.front(); q.pop(); order.push_back(u);
for (int v : g[u]) if (--indeg[v] == 0) q.push(v);
} |
Dijkstra
nonnegative weights
O((V + E) log V) |
import heapq
def dijkstra(g, src):
INF = float("inf")
dist = [INF] * len(g)
dist[src] = 0
pq = [(0, src)]
while pq:
d, u = heapq.heappop(pq)
if d != dist[u]: continue
for v, w in g[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v))
return dist |
type Item struct { d, u int }
// heap.Interface; Less by smaller d
heap.Push(&pq, Item{0, s})
for pq.Len() > 0 {
it := heap.Pop(&pq).(Item)
if it.d != dist[it.u] { continue }
// relax Edge{to,w}; push Item{nd,to}
} |
type P = [d: number, u: number]
const pq = new MinHeap<P>((a, b) => a[0] - b[0])
pq.push([0, s])
while (pq.size()) {
const [d, u] = pq.pop()!
if (d !== dist[u]) continue
// relax [v,w]; push [nd,v]
} |
using P = pair<int, int>;
priority_queue<P, vector<P>, greater<P>> pq;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d != dist[u]) continue;
// relax pair{v,w}; push {nd,v}
} |
| operation | Python | Go | TypeScript | C++ |
|---|
4 directions
O(1) |
DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1)) |
dirs := [][2]int{{1,0}, {-1,0}, {0,1}, {0,-1}} |
const dirs: [number, number][] = [[1,0], [-1,0], [0,1], [0,-1]] |
int dirs[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}}; |
neighbors
O(RC) |
rows, cols = len(grid), len(grid[0])
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
visit(nr, nc) |
rows, cols := len(grid), len(grid[0])
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if 0 <= nr && nr < rows && 0 <= nc && nc < cols { visit(nr, nc) }
} |
const rows = grid.length, cols = grid[0].length
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc
if (0 <= nr && nr < rows && 0 <= nc && nc < cols) visit(nr, nc)
} |
int rows = grid.size(), cols = grid[0].size();
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (0 <= nr && nr < rows && 0 <= nc && nc < cols) visit(nr, nc);
} |
| Python | Go | TypeScript | C++ |
|---|
- Recursive DFS hits the default recursion limit on deep graphs; prefer an explicit stack for big inputs.
- In BFS, mark visited when enqueuing, not when popping, or parallel edges can enqueue the same node many times.
heapq has no decrease-key; push the new distance and skip stale (d, node) pairs.
|
- Use
_, ok := seen[v]; reading a missing map key returns the zero value.
- Keep a queue head index; repeatedly slicing from the front can retain old backing-array storage.
container/heap stores any; Push/Pop usually need pointer receivers and type assertions.
|
Array.shift() is O(n); BFS queues should use head++.Set<[number, number]> compares array identity; encode grid cells as strings or ids.- There is no built-in heap; sorting the queue on every Dijkstra step is too slow.
|
- Recursive DFS can overflow the process stack; iterative DFS is safer on hostile depth.
priority_queue<pair<int,int>> is a max-heap and pairs compare first, then second; store {dist, node} with greater<>.- Self-loops block Kahn topo sort; parallel edges must increment and decrement indegree once per edge.
|