Graph, Grid, BFS/DFS, And Union-Find

What's being tested

These problems test graph modeling from strings, grids, and matrices, then choosing the right traversal: BFS for shortest path, DFS for connected components/topological ordering, and memoized DFS for DAG-style dynamic programming. Interviewers are probing correctness on edge cases, complexity discipline, and clean implementation under Meta-style time pressure.

Patterns & templates

• Grid BFS shortest path — use deque, mark visited on enqueue, explore 4 or 8 directions; O(mn) time and space.

• Island counting — scan every cell, launch dfs(r,c) or iterative stack on unvisited land; mutate grid or maintain visited.

• Longest increasing path — model matrix as DAG by value order; dfs(r,c) with memo[r][c] gives O(mn).

• Topological sort for unknown alphabet — build directed edges from first differing chars, then use in_degree + queue; detect cycles.

• Custom lexicographic validation — map char -> rank, compare adjacent words only; handle prefix invalid case like "abc" before "ab".

• Union-Find alternative for components — find, union, path compression, union by rank; useful when connections are streamed or repeated.

• Sparse representation — for sparse dot product, store {index: value} or sorted pairs; iterate over smaller map for O(min(k1,k2)).

Common pitfalls

Pitfall: Marking grid nodes visited only when popped from BFS can enqueue the same cell many times and distort shortest-path logic.

Pitfall: In alien dictionary, adding constraints from every character position is wrong; only the first differing character between adjacent words matters.

Pitfall: Recursive DFS can hit recursion limits on large grids; mention iterative stack or recursion-limit handling if dimensions are large.

Practice these

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