Grid Simulation And Spatial Reasoning

What's being tested

These problems assess spatial reasoning over a discrete grid plus stateful simulation: placing, moving, and resolving interactions of shapes on a matrix. Interviewers probe correctness (bounds, collisions), algorithmic complexity, and robust handling of repeated state changes (pops, gravity, rotations).

Patterns & templates

• Coordinate system conventions — pick (row, col) or (x, y) and stick to it; convert rotations via simple transforms: (r,c) → (c, -r).

• Bounding-box / collision check before placement — test all cells of a piece against grid bounds and non-empty cells, O(k) per placement where k = piece cells.

• Column compaction (gravity) implemented per-column in one pass: write-pointer sinks non-empty cells down, O(rows*cols) time, O(1) extra space.

• Connected-component removal for match/pops — use dfs/bfs to find same-colored regions; mark-then-remove to avoid mid-traversal mutation.

• Iterative simulation loop: detect removals → collapse columns → repeat until stable; count iterations to bound runtime.

• In-place vs. copy tradeoff — mutate grid in-place for memory, but copy snapshot when you need simultaneous-read semantics.

• Bitmask/encoding optimization for tiny grids — pack rows into integers to speed checks and rotations when memory/CPU matters.

Common pitfalls

Pitfall: Off-by-one bounds checks — forgetting inclusive/exclusive ranges when mapping piece cells to grid indices causes silent out-of-bounds writes.

Pitfall: Mutating grid while traversing — removing cells during DFS/BFS can skip neighbors; instead mark removals, then apply them in a separate pass.

Pitfall: Assuming single-pass gravity — cascaded pops require repeating detect→remove→collapse until no changes, or you’ll produce incorrect final state.

Practice these

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