Blind 75 — Graph Pattern Guide

How to Identify a “Graph” Problem

Interview Triggers

• Nodes + edges, adjacency list/matrix
• “Connected components”, “is it connected”, “is there a cycle”
• “Course schedule” / dependency order → topological sort
• 2-D grid where cells are nodes (LC 200, 417)
• “Clone / copy the graph”
• Words → graph (alien dictionary)

Which Sub-Pattern Does It Belong To?

If the prompt says…	Use this sub-pattern	Example LC
“Deep copy a graph”	BFS/DFS + HashMap clone	133
“Can finish all courses given prerequisites?”	Topological sort / cycle detect	207
“Cells that can flow to both oceans”	Multi-source reverse DFS/BFS	417
“Count islands in a grid”	Flood fill (DFS/BFS)	200
“Longest consecutive run of numbers”	HashSet + start-of-sequence	128
“Words form a valid dictionary order”	Topological sort from letters	269
“Is this edge list a valid tree?”	Union-Find + n-1 edges	261
“Count connected components”	Union-Find or DFS	323

---

The Decision Tree

GRAPH PROBLEM
│
├─ Shortest path / level-order info?
│   └─ BFS (LC 102 tree, LC 200 grid)
│
├─ Need to visit all reachable nodes?
│   └─ DFS (LC 200, 133, 417)
│
├─ Dependency / ordering?
│   └─ Topological sort (Kahn's BFS or DFS) → LC 207, 269
│
├─ Connectivity / merge groups?
│   └─ Union-Find (DSU) → LC 261, 323
│
├─ Cycle detection?
│   ├─ Directed   → DFS color states (white/gray/black) or Kahn's
│   └─ Undirected → Union-Find or DFS parent tracking
│
└─ 2-D grid → treat each cell as a node
    └─ Flood fill = DFS/BFS (LC 200)

---

Traversal Templates

DFS (Recursive)

void dfs(int node, boolean[] visited, List<List<Integer>> adj) {
    if (visited[node]) return;
    visited[node] = true;
    for (int neighbor : adj.get(node)) dfs(neighbor, visited, adj);
}

BFS (Queue)

void bfs(int start, List<List<Integer>> adj) {
    Queue<Integer> q = new ArrayDeque<>();
    boolean[] visited = new boolean[adj.size()];
    q.offer(start); visited[start] = true;
    while (!q.isEmpty()) {
        int node = q.poll();
        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) { visited[neighbor] = true; q.offer(neighbor); }
        }
    }
}

Topological Sort (Kahn’s)

int[] indegree = new int[n];
// build indegree from edges
Queue<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indegree[i] == 0) q.offer(i);
int count = 0;
while (!q.isEmpty()) {
    int u = q.poll(); count++;
    for (int v : adj.get(u)) if (--indegree[v] == 0) q.offer(v);
}
return count == n; // false = cycle exists

Union-Find (DSU)

int[] parent;
int find(int x) { return parent[x] == x ? x : (parent[x] = find(parent[x])); }
boolean union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return false;
    parent[ra] = rb;
    return true;
}

---

Bread & Butter Problems

#	Problem	LC #	Difficulty	Sub-Pattern
1	Number of Islands	200	Medium	Flood fill
2	Clone Graph	133	Medium	DFS/BFS + Map
3	Course Schedule	207	Medium	Topo sort

FAANG “Aha!” Problems

#	Problem	LC #	Difficulty	Sub-Pattern
1	Pacific Atlantic Water Flow	417	Medium	Multi-source DFS
2	Longest Consecutive Sequence	128	Medium	HashSet streak
3	Graph Valid Tree	261	Medium	Union-Find
4	Number of Connected Components	323	Medium	Union-Find / DFS
5	Alien Dictionary	269	Hard	Topo sort

---

Java Implementation Tips

• Adjacency list: List<List<Integer>> adj — initialize with for (int i=0;i<n;i++) adj.add(new ArrayList<>());
• Use ArrayDeque over LinkedList for queue — faster, no nulls allowed.
• For recursive DFS on deep graphs, watch stack depth (~10^4 in Java). Convert to iterative if needed.
• Visited tracking: boolean[] (faster) over Set<Integer>.
• For grid problems, use direction array: int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};

---

Senior Mental Trigger

“Level-by-level → BFS. Explore-everything → DFS. Ordering → Topo. Grouping → Union-Find.”