Implement a match-3 board resolver

Question

Implement a match-3 board resolver (the core loop of a "candy crush"-style game). You are given an m×n grid of cells. Each cell holds a value identifying its type — e.g. a color character such as 'R'/'G'/'B', or an integer code (use whichever the interviewer specifies; the value just needs to be comparable). Repeatedly resolve the board until it stabilizes, then return the final state.

On each pass:

1. Detect matches. Find every cell that belongs to a run of three or more of the same value aligned horizontally or vertically (an L/T shape counts because it is the union of a qualifying horizontal run and a qualifying vertical run — a diagonal does not count). Mark all such cells for removal.
2. Remove matches. Clear all marked cells simultaneously.
3. Apply gravity. Within each column, surviving cells fall straight down to fill the gaps left by removals. The emptied cells surface at the top of each column. State your choice for how to represent an empty cell — a blank/sentinel, or a fixed filler value such as 0.
4. Chain reactions. Gravity can create new runs of three or more, so repeat steps 1–3 until a full pass produces no further removals (the board is stable).

Return the final board state and the total number of cells removed across all passes.

Discuss your data structures, how you detect groups, how gravity is implemented per column, the termination condition, and the time/space complexity of the whole process.