Graphs, Grids, And Reachability

What's being tested

These problems test graph traversal, reachability, and choosing the right representation for directed, undirected, and grid graphs. You must distinguish BFS for unweighted shortest paths, DFS/Union-Find for connectivity, and state tracking for cycle detection, while stating time and space complexity clearly.

Patterns & templates

• BFS shortest path — use a queue and distance map for unweighted graphs; runs in O(V + E) time and returns minimum hop count.

• DFS reachability — recursively or iteratively explore neighbors with a visited set; avoid revisiting nodes, especially when graphs have cycles.

• Multi-source ancestor search — traverse parent links from each person, store all reachable ancestors, then intersect sets to test shared ancestry.

• Directed meeting node — compute distances from both starts independently, scan nodes reachable from both, minimize max(distA[i], distB[i]), then break ties by index.

• Grid traversal — model four-neighbor movement with direction vectors; mark cells visited immediately to prevent duplicate island counts.

• Cycle detection — undirected graphs need parent tracking or Union-Find; directed graphs need three-state DFS: unvisited, active, and completed.

• Obstacle handling — reject blocked start or destination, check bounds before indexing, and use BFS when every legal move has equal cost.

Common pitfalls

Pitfall: Marking a node visited only when dequeued can enqueue it repeatedly; mark it when discovered instead.

Pitfall: Treating directed edges as bidirectional changes reachability and can incorrectly identify paths, ancestors, or cycles.

Pitfall: Claiming O(V + E) without defining V and E; for a grid, state V = rows × columns and explain memory usage.

Practice these

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