Graph, Grid, And Connectivity Algorithms

What's being tested

Graph/grid connectivity questions test whether you can model cells or entities as nodes, traverse components correctly, and preserve invariants under edge cases like cycles, wrap-around, or repeated shapes. Interviewers look for clean DFS/BFS, Union-Find, topological sort, and proof-level reasoning about correctness and complexity.

Patterns & templates

• Grid DFS/BFS components — scan every cell, start traversal on unvisited land; O(R*C) time, O(R*C) worst-case space.

• Distinct island normalization — record relative coordinates from an origin, e.g. (r-r0, c-c0); sort/serialize shape to compare patterns.

• Bipartite graph coloring — assign colors with BFS/DFS; conflict on same-color edge means impossible; handle disconnected components.

• Topological sort — use Kahn’s algorithm with indegrees or postorder DFS; cycle exists if processed count < n.

• Dynamic connectivity — use Disjoint Set Union with path compression and union by rank; near-constant amortized α(n) operations.

• Torus grid adjacency — compute neighbors with modulo: (r+dr+R)%R, (c+dc+C)%C; beware duplicate neighbors in tiny grids.

• Monotonic deque — for sliding maximum, keep indices in decreasing value order; O(n) time, remove expired front indices.

Common pitfalls

Pitfall: Treating diagonal cells as connected when the problem only allows 4-directional adjacency.

Pitfall: Counting distinct islands by traversal string without stable direction markers or relative coordinates, causing different shapes to collide.

Pitfall: Running topological sort from only one node; disconnected graph components must all be initialized or visited.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.