LeetCode · Graphs
Graphs Problem Set
BFS, DFS, multi-source BFS, topological sort, union-find, and shortest path. Graph problems are about traversal strategy and state tracking.
| Difficulty | Pattern | Problem | Key Insight |
|---|---|---|---|
| Medium | BFS/DFS | LC 200 · Number of Islands | Flood-fill connected components on grid. O(m·n). |
| Medium | multi-source BFS | LC 994 · Rotting Oranges | Start from every rotten orange at once. Each BFS layer is one minute of spread. |
| Medium | multi-source BFS | LC 542 · 01 Matrix | Reverse the search: BFS from all 0-cells to fill the nearest-zero distance for every 1-cell. |
| Medium | DFS | LC 133 · Clone Graph | DFS/BFS with HashMap old→new. O(V+E). |
| Medium | BFS/DFS | LC 695 · Max Area of Island | DFS counting cells per component. O(m·n). |
| Medium | BFS/DFS | LC 417 · Pacific Atlantic Water Flow | BFS/DFS from both oceans, intersect reachable sets. O(m·n). |
| Medium | topo-sort | LC 207 · Course Schedule | Cycle detection via topological sort (Kahn's or DFS). O(V+E). |
| Medium | topo-sort | LC 210 · Course Schedule II | Topological ordering via BFS (Kahn's). O(V+E). |
| Medium | union-find | LC 323 · Number of Connected Components | Union-Find or DFS on adjacency list. O(V+E). (Premium) |
| Medium | union-find | LC 684 · Redundant Connection | Union-Find: first edge that creates a cycle. O(n · α(n)). |
| Medium | shortest-path | LC 743 · Network Delay Time | Dijkstra from source, return max distance. O((V+E) log V). |
| Hard | BFS | LC 127 · Word Ladder | BFS on word graph with wildcard patterns. O(m²·n). |