| A Star Search |
O(E log V) with a good heuristic (grid: E ~ 4V) |
Shortest path when you have a good heuristic (estimated distance to goal). |
| Bellman Ford |
O(V * E) |
Shortest paths with negative edge weights — currency arbitrage |
| Clone Graph |
O(V + E) |
Graph deep copy — "clone graph", "copy linked structure with cycles". |
| Course Schedule |
O(V + E) |
Cycle detection in a directed graph — "can all tasks be completed?", |
| Dijkstra |
O((V + E) log V) |
Shortest path with NON-NEGATIVE weights. Flight routing, network latency, |
| Geohash Grid |
--- |
Spatial indexing for proximity queries — "find nearby points", |
| Kd Tree |
--- |
Nearest neighbor in multi-dimensional space — "closest point", |
| Minimum Spanning Tree |
--- |
Minimum cost to connect all nodes — cable/road/pipeline routing, |
| Network Delay Time |
O((V + E) log V) |
"Can a signal/message reach all nodes, and how long?" — broadcast |
| Network Flow |
O(V * E^2) |
Maximum throughput — "max bandwidth", "maximum matching", "supply |
| Number Of Islands |
O(m * n) — each cell visited at most once |
Connected components / flood fill — "count islands", "count regions", |
| Topological Sort |
O(V + E) |
Dependency resolution — "build order", "task scheduling with prereqs", |
| Word Ladder |
O(n * m^2) where n = |word_list|, m = word length |
BFS for shortest transformation sequence — "minimum edits", "fewest |