We use cookies for site analytics. Accept to help us understand how the site is used. See our Privacy Policy for details.
Union-find keeps a forest of disjoint sets with near-constant find and union once you add path compression and union by rank. It beats DFS whenever connectivity queries are interleaved with edge additions, and it detects cycles in an undirected graph almost incidentally. Short to implement, and instantly recognisable to an interviewer as the right tool.
"Are these two connected?", counting components, or detecting a cycle in an undirected graph.
5 problems. Each one runs in an in-browser editor against real test cases, with hints and a worked solution.
The patterns cheat sheet covers all of these in one page - what each one looks like in a problem statement, and the template that follows.