Bricks Falling When Hit

Bricks Falling When Hit

What is this problem about?

Bricks Falling When Hit is a challenging "Hard" problem involving a grid of bricks. Some bricks are connected to the top of the grid directly or indirectly. When a brick is "hit," it is removed. If any other bricks were only connected to the top through the removed brick, they also fall. Given a series of hits, you need to return how many bricks fall after each hit.

Why is this asked in interviews?

Companies like Google and Snap ask this to test your ability to handle dynamic connectivity in a graph. It requires thinking "backwards"—instead of removing bricks and seeing what falls, it's often easier to see what bricks become connected as you add them back in reverse order. It's an excellent test of the Union Find data structure.

Algorithmic pattern used

The primary pattern is the Union Find (Disjoint Set Union) interview pattern, processed in reverse. First, you remove all bricks that will be hit. Then, you use Union Find to find all bricks still connected to the top. Then, you iterate through the hits in reverse order, "adding" the bricks back and checking how many new bricks become connected to the top because of the addition.

Example explanation

Grid: 1 1 1 0 1 0 0 0 0 Hit at (1,1).

1. Initially, all bricks (1,0), (1,1), (1,2), (2,1) are connected to the top.
2. After hitting (1,1), the brick at (2,1) loses its only connection to the top and falls.
3. In reverse: Start with (1,1) removed. Only (1,0), (1,1), (1,2) are at the top.
4. Add back (1,1). Now (2,1) becomes connected to the top. 1 brick falls (or in reverse, 1 brick is "rescued").

Common mistakes candidates make

A common mistake is trying to perform a BFS or DFS after every single hit, which is $O(H imes R imes C)$ and too slow. Another error is forgetting that a brick might already be connected to the top through another path even after its primary path is broken. The "reverse processing" trick is the key to solving this in $O((H + RC) \alpha(RC))$ time.

Interview preparation tip

When a problem involves "removing" things and checking connectivity, always consider if processing the removals in reverse (as additions) simplifies the problem. Union Find is much better at adding connections than removing them.