Problem Description

You have a grid of bricks represented as an m x n binary matrix where 1 represents a brick and 0 represents empty space. A brick remains stable (doesn't fall) if it meets one of these conditions:

• It's in the top row (directly connected to the ceiling), OR
• At least one of its 4 adjacent neighbors (up, down, left, right) is stable

You're given a list of hits, where each hits[i] = (row_i, col_i) represents erasing the brick at that position. When you erase a brick:

• If there's no brick at that position, nothing happens
• If there's a brick, it disappears
• Any bricks that become unstable as a result will immediately fall and disappear (they don't land on other bricks below)

Your task is to return an array where result[i] represents how many bricks fall after applying the i-th hit.

Key Points:

• Bricks fall if they lose their connection to the top row (either directly or through other stable bricks)
• When bricks fall, they completely disappear from the grid
• A hit on an empty cell causes no bricks to fall
• The hits are applied sequentially, and each hit affects the grid state left by previous hits

Example scenario: If hitting a brick causes a cluster of bricks to lose their only connection to the top row, all bricks in that cluster will fall and be counted in the result for that hit.

Intuition

The key insight is to think about this problem in reverse. Instead of removing bricks and watching them fall, we can start with all the hits already applied (all bricks already removed), then add the bricks back one by one in reverse order.

Why does this help? When we remove a brick, it's hard to track which bricks will fall because we need to check if they still have a path to the top. But when we add a brick back, we can easily count how many previously disconnected bricks now become connected to the top through this newly added brick.

Think of it like this: imagine a group of floating bricks that aren't connected to the ceiling. When we place a brick that bridges them to the ceiling, all those floating bricks suddenly become stable. The number of bricks that "would have fallen" when we removed this brick is exactly the number of floating bricks that became stable when we added it back.

This naturally leads us to use Union-Find (Disjoint Set Union) data structure. We can treat all bricks connected to the top row as one giant component. Here's the process:

1. Start with the final state (all hits applied)
2. Create a virtual "super root" representing the ceiling
3. Connect all top-row bricks to this super root
4. Build the initial connected components
5. Process hits in reverse order:
   • When adding a brick back, check how many bricks were in the "ceiling component" before
   • Add the brick and connect it to its neighbors
   • Check how many bricks are in the "ceiling component" after
   • The difference (minus 1 for the brick we just added) tells us how many bricks would have fallen when this brick was originally removed

The beauty of this approach is that Union-Find efficiently tracks component sizes, so we can quickly determine how many previously disconnected bricks become connected to the ceiling when we add each brick back.

Learn more about Union Find patterns.

Solution Approach

The solution implements the reverse-time Union-Find approach. Let's walk through the implementation step by step:

1. Union-Find Setup:

• Create a parent array p of size m * n + 1 where each cell (i, j) maps to index i * n + j
• The extra position m * n serves as the "super root" representing the ceiling
• Initialize size array to track component sizes

2. Apply All Hits First:

g = deepcopy(grid)
for i, j in hits:
    g[i][j] = 0

Create a copy of the grid and remove all bricks that will be hit, giving us the final state.

3. Build Initial Connected Components:

# Connect top row bricks to the super root
for j in range(n):
    if g[0][j] == 1:
        union(j, m * n)

# Connect remaining bricks to their neighbors
for i in range(1, m):
    for j in range(n):
        if g[i][j] == 0:
            continue
        if g[i - 1][j] == 1:  # Connect to brick above
            union(i * n + j, (i - 1) * n + j)
        if j > 0 and g[i][j - 1] == 1:  # Connect to brick on left
            union(i * n + j, i * n + j - 1)

We only check up and left directions to avoid duplicate unions (the down and right neighbors will check up and left respectively).

4. Process Hits in Reverse:

for i, j in hits[::-1]:
    if grid[i][j] == 0:  # Original position had no brick
        ans.append(0)
        continue
  
    g[i][j] = 1  # Add brick back
    prev = size[find(m * n)]  # Size of ceiling component before
  
    if i == 0:
        union(j, m * n)  # Connect to ceiling if in top row
  
    # Connect to all 4 neighbors
    for a, b in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        x, y = i + a, j + b
        if 0 <= x < m and 0 <= y < n and g[x][y] == 1:
            union(i * n + j, x * n + y)
  
    curr = size[find(m * n)]  # Size of ceiling component after
    ans.append(max(0, curr - prev - 1))

For each hit in reverse:

• If the original grid had no brick at this position, 0 bricks fall
• Otherwise, add the brick back and measure the change in the ceiling component size
• The number of bricks that fell = (new size - old size - 1), where we subtract 1 for the brick we just added
• Use max(0, ...) to handle edge cases where the brick wasn't connected to ceiling

5. Return Results in Original Order:

return ans[::-1]

Since we processed hits in reverse, reverse the answer array to match the original hit order.

Time Complexity: O(k * α(m*n)) where k is the number of hits and α is the inverse Ackermann function (practically constant)

Space Complexity: O(m * n) for the Union-Find structure and grid copy

Example Walkthrough

Let's work through a small example to illustrate the solution approach.

Initial Setup:

Grid (2x3):        Hits: [(1,1), (0,1)]
[1, 1, 1]          
[0, 1, 0]          

Step 1: Apply all hits to get final state

After all hits:
[1, 0, 1]
[0, 0, 0]

Step 2: Build Union-Find with ceiling connection

• Create super root at index 6 (since we have 2×3 = 6 cells)
• Connect top row bricks to ceiling:
  • Cell (0,0) → index 0 → connects to 6
  • Cell (0,2) → index 2 → connects to 6
• No other bricks to connect to neighbors

Current state: Two bricks connected to ceiling through super root 6. Component size at root 6: 3 (brick at index 0 + brick at index 2 + super root)

Step 3: Process hits in reverse order

Processing Hit #2 (originally at index 1): Position (0,1)

• Original grid had brick here (grid[0][1] = 1)
• Previous ceiling size: 3
• Add brick back at (0,1):

  [1, 1, 1]
  [0, 0, 0]

• Since it's in top row, connect to ceiling (index 1 → 6)
• Check 4 neighbors:
  • Left (0,0): has brick, union(1, 0) - already connected via ceiling
  • Right (0,2): has brick, union(1, 2) - already connected via ceiling
• New ceiling size: 4
• Bricks that fell: 4 - 3 - 1 = 0

Processing Hit #1 (originally at index 0): Position (1,1)

• Original grid had brick here (grid[1][1] = 1)
• Previous ceiling size: 4
• Add brick back at (1,1):

  [1, 1, 1]
  [0, 1, 0]

• Not in top row, don't connect directly to ceiling
• Check 4 neighbors:
  • Up (0,1): has brick, union(4, 1) - connects this brick to ceiling!
• New ceiling size: 5
• Bricks that fell: 5 - 4 - 1 = 0

Step 4: Reverse the results Results in reverse: [0, 0] Final answer: [0, 0]

Why this makes sense:

• Hit at (1,1): The brick at (1,1) was connected to ceiling through (0,1), so removing it doesn't cause any falls
• Hit at (0,1): This is a ceiling brick surrounded by other ceiling bricks, removing it doesn't disconnect anything

Let's consider a different example where bricks actually fall:

Example 2:

Grid (3x2):        Hits: [(1,0), (0,0)]
[1, 1]          
[1, 0]
[1, 0]          

After applying all hits:

[0, 1]
[0, 0]
[1, 0]

The brick at (2,0) is now disconnected from ceiling!

Processing in reverse:

• Add back (0,0): Connects (2,0) to ceiling through (1,0) → 1 brick saved from falling
• Add back (1,0): Just connects to existing ceiling component → 0 bricks fall

Final answer: [0, 1] (reversed from [1, 0])

This shows how the reverse approach elegantly counts falling bricks by measuring how many disconnected bricks become connected when we add each brick back.

Solution Implementation

Time and Space Complexity

Time Complexity: O(k * m * n * α(m * n)) where k is the number of hits, m and n are the dimensions of the grid, and α is the inverse Ackermann function.

• Initial setup and copying the grid takes O(m * n) time
• Removing all hit bricks: O(k) time
• Building the initial union-find structure after removing hits:
  • First row union with virtual root: O(n * α(m * n))
  • Remaining cells union operations: O(m * n * α(m * n))
• Processing hits in reverse order: For each of the k hits:
  • Finding the size before adding the brick: O(α(m * n))
  • Union operations with up to 4 neighbors: O(4 * α(m * n))
  • Finding the size after adding the brick: O(α(m * n))
  • Total per hit: O(α(m * n))
• Overall for all hits: O(k * α(m * n))

Since α(m * n) is practically constant (at most 4 for any reasonable input size), the time complexity can be considered O(m * n + k) in practice, but theoretically it's O((m * n + k) * α(m * n)).

Space Complexity: O(m * n)

• The parent array p uses O(m * n + 1) space
• The size array uses O(m * n + 1) space
• The copied grid g uses O(m * n) space
• The answer array uses O(k) space
• Total space complexity is O(m * n) since typically k ≤ m * n

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Checking if Original Grid Had a Brick

Pitfall: A common mistake is forgetting to check whether the original grid actually had a brick at the hit position. If you process a hit on an already empty cell (where grid[i][j] == 0 originally), you might incorrectly calculate fallen bricks when reversing the operation.

Why it happens: When processing hits in reverse, we add bricks back. But if there was never a brick at that position originally, we shouldn't add one back.

Incorrect approach:

for row_idx, col_idx in reversed(hits):
    # WRONG: Not checking if original grid had a brick
    grid_after_hits[row_idx][col_idx] = 1
    # ... rest of the logic

Correct approach:

for row_idx, col_idx in reversed(hits):
    if grid[row_idx][col_idx] == 0:  # Original grid had no brick
        result.append(0)
        continue
  
    grid_after_hits[row_idx][col_idx] = 1  # Only add if originally present
    # ... rest of the logic

2. Incorrect Calculation of Fallen Bricks

Pitfall: Forgetting to subtract 1 from the difference in ceiling component sizes, which leads to counting the newly added brick itself as a "fallen" brick.

Why it happens: When we add a brick back and it connects to the ceiling, the ceiling component size increases. This increase includes both the newly added brick AND any previously disconnected bricks that now reconnect through it.

Incorrect approach:

fallen_bricks = stable_bricks_after - stable_bricks_before
# WRONG: This counts the added brick as fallen

Correct approach:

fallen_bricks = max(0, stable_bricks_after - stable_bricks_before - 1)
# Subtract 1 to exclude the brick we just added
# Use max(0, ...) to handle cases where brick doesn't connect to ceiling

3. Union-Find Path Compression Bug

Pitfall: Implementing path compression incorrectly by not updating the parent pointer during the recursive find operation.

Incorrect approach:

def find(node: int) -> int:
    if parent[node] != node:
        return find(parent[node])  # WRONG: No path compression
    return parent[node]

Correct approach:

def find(node: int) -> int:
    if parent[node] != node:
        parent[node] = find(parent[node])  # Compress path
    return parent[node]

4. Modifying Original Grid Instead of Using a Copy

Pitfall: Directly modifying the input grid when applying all hits initially, which corrupts the data needed to check if a position originally had a brick.

Incorrect approach:

# WRONG: Modifying original grid
for i, j in hits:
    grid[i][j] = 0

# Later when processing in reverse:
if grid[i][j] == 0:  # This check is now meaningless!
    result.append(0)

Correct approach:

# Create a copy to preserve original grid
grid_after_hits = [row[:] for row in grid]
for i, j in hits:
    grid_after_hits[i][j] = 0

# Original grid remains intact for checking
if grid[i][j] == 0:  # Can correctly check original state
    result.append(0)

5. Double-Counting Connections When Building Initial Components

Pitfall: Connecting bricks in all four directions when building the initial Union-Find structure, which unnecessarily doubles the work and could lead to subtle bugs if not handled consistently.

Why it happens: If you check all 4 neighbors for each brick, you'll process each edge twice (once from each endpoint).

Less efficient approach:

# Checking all 4 directions for every brick
for i in range(m):
    for j in range(n):
        for di, dj in [(0,1), (0,-1), (1,0), (-1,0)]:
            # This processes each edge twice

More efficient approach:

# Only check up and left (or down and right)
for i in range(1, m):
    for j in range(n):
        if grid_after_hits[i][j] == 0:
            continue
        # Check only up
        if grid_after_hits[i-1][j] == 1:
            union(i*n+j, (i-1)*n+j)
        # Check only left
        if j > 0 and grid_after_hits[i][j-1] == 1:
            union(i*n+j, i*n+j-1)

These pitfalls are particularly tricky because they might not cause obvious errors in simple test cases but will fail on edge cases or larger inputs.