Match-3 Board Simulation

What's being tested

Match-3 board simulation tests grid scanning, repeated state mutation, and termination when no more eliminations exist. Interviewers are probing whether you can separate detection from deletion, apply gravity correctly, and reason about complexity over multiple cascades.

Patterns & templates

• Two-phase update: first mark all crushable cells, then mutate; deleting during scan causes missed overlapping horizontal/vertical matches.

• Row/column run detection: scan consecutive equal nonzero values with while loops; mark runs where length >= 3.

• Marker encoding: use negative values or a separate to_crush boolean grid; preserve original candy type while detecting overlapping groups.

• Gravity compaction: for each column, write non-crushed values from bottom to top using write_row, then fill remaining cells with 0.

• Fixed-point iteration: repeat detect -> crush -> gravity until no cells are marked; worst-case time is O(kmn) for k cascades.

• Connected group variant: if removal is by connected components instead of straight runs, use BFS/DFS with visited and size threshold checks.

• Clean function split: implement find_matches(board), apply_gravity(board), and resolve(board) to simplify debugging and interviewer follow-ups.

Common pitfalls

Pitfall: Mutating cells to 0 during detection can break detection of crossing matches, such as a horizontal and vertical run sharing one cell.

Pitfall: Gravity must preserve vertical order within each column; sorting or rebuilding incorrectly changes relative candy positions.

Pitfall: Forgetting the loop termination condition leads to returning after one crush instead of resolving all cascades.

Practice these

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