Grid, Matrix And Spatial Algorithms

What's being tested

Grid and matrix algorithms here test whether you can model 2D state cleanly, choose the right traversal strategy, and reason about boundaries, mutation, and complexity. Expect divide-and-conquer, DFS/backtracking, dynamic programming, and graph reachability patterns rather than heavy system design.

Patterns & templates

• QuadTree recursion with build(r0, c0, size) — check uniform region, otherwise split into four quadrants; O(n^2 log n) naive, O(n^2) with prefix sums.

• 2D prefix sums for constant-time area checks — compute sum(r1,c1,r2,c2); uniform binary square if sum is 0 or area.

• Word search DFS/backtracking using dfs(r, c, i) — mark visited, explore 4 directions, unmark on return; worst case O(mn * 4^L).

• Fixed-direction grid scanning for simpler word search — test 8 directions with (dr, dc) arrays; complexity O(mn * D * L).

• Largest square DP in binary matrices — dp[i][j] = 1 + min(top, left, diag) when cell matches; O(mn) time, O(n) space possible.

• Graph eventual safety via DFS coloring — 0=unvisited, 1=visiting, 2=safe; cycles are unsafe, terminal-reaching DAG paths are safe.

• Boundary helpers like in_bounds(r,c) and direction arrays reduce off-by-one bugs; clarify diagonal moves, cell reuse, and empty input early.

Common pitfalls

• Pitfall: Reusing a cell in word search accidentally because visited state is not restored during backtracking.

• Pitfall: Building QuadTrees by rescanning every subgrid without discussing prefix-sum optimization or worst-case complexity.

• Pitfall: Treating “can reach a terminal node” as equivalent to “all paths eventually reach a terminal node” in graph safety problems.

Practice these

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