Coding

Graphs

Adjacency lists + visited sets; BFS/DFS/topological sort.

Coding pattern

Overview

Graph problems model entities and their relationships as nodes and edges. The first move is always representation (adjacency list, directed vs weighted); from there traversal, cycle detection, and shortest-path techniques answer connectivity and reachability questions.

How it works

Coding pattern

ClientServiceEdgeData

Step by step, with examples

1
Nodes+edges
- Build an adjacency list; note directed/weighted.
2
BFS/DFS
- Visit neighbors and mark them visited.
3
Order/detect
- Topo-sort, detect cycles, or count components.
4
Result
- Return a path, order, or component count.
- Example: Course schedule

When to reach for it

Connectivity
Shortest path (unweighted)
Dependency ordering

Example problem

Course Schedule — can all courses be finished (cycle detection)?

Approach

Build adjacency + in-degree
BFS over zero in-degree nodes (Kahn's algorithm)
If processed count < n, a cycle exists

Solution

function canFinish(n, prereqs) {
  const adj = Array.from({length:n},()=>[]), indeg = Array(n).fill(0);
  for (const [a,b] of prereqs){ adj[b].push(a); indeg[a]++; }
  const q = []; for(let i=0;i<n;i++) if(!indeg[i]) q.push(i);
  let seen = 0;
  while(q.length){ const c = q.pop(); seen++;
    for(const nx of adj[c]) if(--indeg[nx]===0) q.push(nx); }
  return seen === n;
}

Complexity

Time O(V + E), Space O(V + E).

Common pitfalls

Not detecting cycles
Re-visiting nodes

Where this content comes from

For full transparency, this content is curated and verified from these sources:

Curated company-tagged problem banksRecurring interview pattern librariesOppZen-authored drills & solutions