Bricks Falling When Hit

Bricks Falling When Hit looks scary, but it is really one classic trick wearing a costume: when a problem is hard going forward, run it in reverse. Removing a brick can drop a whole cluster at once, which is hard to model — but adding a brick only ever glues things together, which union-find loves.

The slow way first

The naive approach: for each hit, erase the brick, then re-run a full flood-fill from the top row to see which bricks are still reachable, and count the ones that disappeared. With H hits and a grid of size N, that is O(H · N) — re-scanning the whole grid for every hit, far too slow when both are large.

The question to ask: what makes the forward direction hard? Deletion. When you remove a brick, a cluster can detach all at once, and union-find has no "un-union" operation. So we flip time around.

The idea: remove all hits, then add them back in reverse

Think of a virtual ROOF node sitting above the top row. A brick is stable exactly when it is in the same union-find component as ROOF. The plan:

1. Erase every hit up front, leaving only the bricks that survive all hits.
2. Union those survivors with their neighbors, and union the top row to ROOF.
3. Walk the hits backward, putting each brick back. Re-adding a brick can reconnect a floating cluster to ROOF. The number of bricks that just became stable, minus the one you added, is how many fell on that original hit.

Why subtract 1? Of the newly-stable bricks, one of them is the brick you just re-added — it was a hit, not a casualty — so it does not count as a brick that fell.

Walk through it

Step through the animation. First the hit (1,0) is erased, leaving (1,1) and (1,2) as a floating cluster — only the top-row brick (0,0) is stuck to the roof. Then we re-add (1,0): it touches (0,0) above (on the roof) and (1,1) beside it, dragging the whole cluster up. Bricks stuck to the roof go from 1 to 4; subtract the brick we added and 2 bricks fell.

Pseudocode

remove every hit from the grid first
union all remaining bricks together, and union the top row to ROOF
result = array of zeros, one per hit
for k from last hit down to first:
    if that cell was originally empty: result[k] = 0; continue
    pre  = number of bricks connected to ROOF
    put the brick back and union it with its neighbors (and ROOF if top row)
    post = number of bricks connected to ROOF
    result[k] = max(0, post - pre - 1)   # the re-added brick itself does not fall
return result

The Python solution

def hit_bricks(grid, hits):
    for r, c in hits:           # remove every hit up front
        grid[r][c] -= 1         # (0 if it was empty, may go to -1)
    union_all_remaining(grid)   # union survivors + top row -> ROOF
    result = [0] * len(hits)
    for k in range(len(hits) - 1, -1, -1):  # walk hits in reverse
        r, c = hits[k]
        if grid[r][c] != 1:     # was empty originally -> no brick to add
            continue
        pre = roof_size()       # bricks stuck before re-adding
        grid[r][c] = 1          # put the brick back
        union_with_neighbors(r, c)
        if r == 0:
            union(node(r, c), ROOF)
        post = roof_size()
        result[k] = max(0, post - pre - 1)  # -1: the brick itself
    return result

• The first loop subtracts 1 at each hit, so an erased brick becomes 0 and a hit on an already-empty cell becomes -1 — a flag we use later to skip it.
• union_all_remaining builds the components once: neighbors get merged, and any top-row brick is merged with the virtual ROOF node. roof_size() is the size of ROOF's component.
• We loop k from the last hit down to the first — the reverse replay.
• A cell that is not 1 here was originally empty (it is now 0 or -1), so there is no brick to re-add; its answer stays 0.
• pre/post bracket the re-add: the jump in ROOF's component size is exactly the cluster that reconnected. Line 16 subtracts 1 for the re-added brick and floors at 0.

Complexity

We pay one pass to build the components, then each re-add is a couple of near-constant union/find operations. The whole job collapses to roughly the size of the grid plus the number of hits.

When this pattern shows up

Practice