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.

Match-3 Board Resolver

Implement the core resolver loop for a match-3 game. You are given a rectangular board where each cell contains a non-negative integer. Positive integers represent candy types, and 0 represents an empty cell. Repeatedly perform passes until the board is stable. In each pass, detect every positive-valued cell that belongs to a horizontal or vertical contiguous run of 3 or more equal values. Mark all such cells, remove them simultaneously by setting them to 0, then apply gravity independently in each column so surviving candies fall downward and empty cells move to the top. Return the final stable board and the total number of cells removed across all passes. Diagonal runs do not count. L/T shapes count only because their horizontal and vertical qualifying runs are both detected; overlapping cells should be removed only once per pass.

Constraints

• 0 <= number of rows m <= 50
• 0 <= number of columns n <= 50
• If m > 0, every row has exactly n columns
• 0 <= board[r][c] <= 10^9
• 0 values are empty and must not be counted as matches

Examples

Example 1

Input: ([])
Output: [[], 0]

Explanation: An empty board is already stable and no cells are removed.

Example 2

Input: ([[1,2,3],[4,5,6],[7,8,9]])
Output: [[[1,2,3],[4,5,6],[7,8,9]], 0]

Explanation: There are no horizontal or vertical runs of 3 or more equal positive values.

Hints

1. Detect matches first and store their positions before clearing anything; removals in the same pass must happen simultaneously.
2. For gravity, process each column from bottom to top with a write pointer that tracks where the next surviving candy should fall.

Solution

The question tests clean grid simulation: a fixed-point loop of detect-match → remove → gravity that repeats until the board is stable. A strong answer detects horizontal and vertical runs of length ≥ 3 with two linear scans into a separate to-remove matrix (so overlapping L/T matches are all caught before any cell is cleared), applies gravity per column so survivors fall down and blanks rise to the top, terminates when a pass removes nothing, accumulates the total cells removed across all cascades, and gives the per-pass O(m·n) cost with the O((m·n)²) worst-case bound over all passes.

This is a grid-simulation problem. The clean structure is a fixed-point loop: mark → remove → gravity, repeated until a pass removes nothing.

1. Detecting matches. You do not need flood-fill / union-find here — matches are strictly horizontal or vertical runs, so two linear scans suffice. Use a separate boolean to_remove[i][j] matrix so that overlapping horizontal and vertical runs (L and T shapes) are all captured before any cell is cleared; clearing in-place mid-scan would corrupt later comparisons.

• Horizontal pass: for each row, walk left to right tracking the start and length of the current equal-value run (skipping/ breaking on empty cells). Whenever a run reaches length ≥ 3, mark every cell in that run.
• Vertical pass: same idea down each column.

2. Removing matches. After both scans, clear every cell flagged in to_remove, and add the number of flagged cells to a running removed_total. Mark them with your chosen empty sentinel.

3. Applying gravity (per column). For each column, collect the surviving (non-empty) values top-to-bottom, then re-stack them at the bottom of the column and fill the top with the empty sentinel (or 0). A two-pointer "write index from the bottom" pass does this in O(m) per column.

4. Termination. Repeat the whole mark → remove → gravity cycle until a pass flags zero cells. That fixed point is guaranteed to be reached because every non-terminal pass strictly decreases the number of non-empty cells (at least three are removed), and the cell count is bounded below by zero.

Reference implementation (Python):

EMPTY = None  # or 0; state your choice

def resolve(board):
    if not board or not board[0]:
        return board, 0
    m, n = len(board), len(board[0])
    removed_total = 0

    while True:
        to_remove = [[False] * n for _ in range(m)]

        # horizontal runs
        for i in range(m):
            j = 0
            while j < n:
                if board[i][j] is EMPTY:
                    j += 1
                    continue
                k = j
                while k < n and board[i][k] == board[i][j]:
                    k += 1
                if k - j >= 3:
                    for c in range(j, k):
                        to_remove[i][c] = True
                j = k

        # vertical runs
        for j in range(n):
            i = 0
            while i < m:
                if board[i][j] is EMPTY:
                    i += 1
                    continue
                k = i
                while k < m and board[k][j] == board[i][j]:
                    k += 1
                if k - i >= 3:
                    for r in range(i, k):
                        to_remove[r][j] = True
                i = k

        # count + clear
        removed_this_pass = 0
        for i in range(m):
            for j in range(n):
                if to_remove[i][j]:
                    board[i][j] = EMPTY
                    removed_this_pass += 1
        if removed_this_pass == 0:
            break
        removed_total += removed_this_pass

        # gravity per column: survivors fall to the bottom, blanks rise to top
        for j in range(n):
            survivors = [board[i][j] for i in range(m) if board[i][j] is not EMPTY]
            write = m - 1
            for v in reversed(survivors):
                board[write][j] = v
                write -= 1
            for i in range(write + 1):
                board[i][j] = EMPTY

    return board, removed_total

Complexity. Each pass is O(m·n): two linear scans for detection, one for clearing, one for gravity. A single pass removes at least three cells, so there are at most O(m·n / 3) = O(m·n) passes in the worst case, giving an overall worst case of O((m·n)²) time. Extra space is O(m·n) for the to_remove matrix (or O(max(m, n)) if you reuse a single row/column buffer and mark cells lazily). In practice the number of cascades is small, so it behaves near-linearly.

Points the interviewer probes:

• Mark-then-remove, not remove-in-place — so overlapping horizontal/vertical matches (L/T shapes) and chain boundaries are detected correctly.
• Gravity direction — survivors fall down; blanks appear at the top. Process each column independently.
• Termination — stop when a pass removes nothing; argue why the loop must terminate.
• Counting — accumulate the total removed across all passes, not just the first.
• Empty-cell convention — pick one (sentinel vs 0) and make detection skip/break on empties so blanks never form a "match".

Given the 3-column board [['R','G','B'],['R','G','B'],['R','G','B']], every column is a vertical run of 3, so all 9 cells are removed; the final board is all-empty and total removed = 9. For [['A','B','B'],['C','B','D'],['E','B','F']] the middle column 'B','B','B' is removed (3 cells); after gravity the remaining cells fall and no new run of 3 forms, so total removed = 3. A board with no run of 3 is returned unchanged with total removed = 0.