Graphs, Grids, And Connected Components

What's being tested

These problems test graph traversal over implicit graphs: grids, pairwise conflict graphs, and connected components. Interviewers are probing whether you can model adjacency correctly, choose DFS, BFS, or Union-Find, and explain correctness plus $O(V+E)$ or $O(mn)$ complexity.

Patterns & templates

• Grid DFS/BFS — write dfs(r, c) with 4-direction deltas; mark visited immediately to avoid duplicate work and cycles.

• Connected components — increment count when finding an unvisited valid node, then flood-fill the entire component; total time is O(nodes + edges).

• Island shape canonicalization — store relative coordinates from the island origin, e.g. (r-r0, c-c0), then serialize to a tuple for set comparison.

• Union-Find — use find, union, path compression, and rank/size when components are dynamic or edges arrive incrementally.

• Conflict graph detection — model exclusions as undirected edges; use coloring with BFS/DFS when checking whether incompatible groups can coexist.

• Boundary handling — centralize in_bounds(r, c) and validity checks; avoid scattered conditionals that cause off-by-one bugs.

• Complexity discipline — for an m x n grid, each cell is visited once: O(mn) time, O(mn) worst-case space for recursion/queue/visited.

Common pitfalls

Pitfall: Marking a grid cell visited after recursive calls can revisit the same cell repeatedly or overflow the stack.

Pitfall: Counting diagonal neighbors as connected unless the prompt explicitly says 8-direction adjacency.

Pitfall: For distinct island shapes, comparing absolute coordinates instead of normalized relative coordinates makes identical translated shapes look different.

Practice these

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