LeetCode 803: Bricks Falling When Hit

Problem Restatement

We are given an m x n grid.

Each cell is either:

A brick is stable if it is connected to the top row, either directly or through other 4-directionally adjacent stable bricks.

We are also given a list of hits. Each hit removes the brick at position (row, col) if a brick exists there.

After each hit, some bricks may no longer be stable. Those bricks fall and disappear. The brick directly hit is not counted as a falling brick.

Return an array where answer[i] is the number of bricks that fall after hits[i] is applied. The erasures are applied sequentially. If a hit targets an empty cell, no bricks fall.

Input and Output

Examples

Example 1:

grid = [[1, 0, 0, 0],
        [1, 1, 1, 0]]

hits = [[1, 0]]

If we remove the brick at (1, 0), the bricks at (1, 1) and (1, 2) lose their connection to the top row.

So the answer is:

[2]

Example 2:

grid = [[1, 0, 0, 0],
        [1, 1, 0, 0]]

hits = [[1, 1], [1, 0]]

First, remove (1, 1). No other brick falls.

Then remove (1, 0). The brick (1, 1) is already gone, so nothing else falls.

The answer is:

[0, 0]

First Thought: Brute Force

A direct simulation is possible.

For each hit:

1. Remove the hit brick if it exists.
2. Start from all bricks in the top row.
3. Use DFS or BFS to mark every stable brick.
4. Every remaining unmarked brick falls.
5. Count those falling bricks and remove them.

This matches the problem definition, but it is too slow.

If the grid has m * n cells and there are k hits, this can cost:

O(k * m * n)

Each hit may force us to scan the whole grid again.

Key Insight

Removing bricks is hard because Union-Find does not support deleting edges easily.

Adding bricks is much easier.

So we process the problem backward.

Instead of applying hits from first to last, we do this:

1. Remove all hit bricks first.
2. Build the connected components of the remaining grid.
3. Add hit bricks back in reverse order.
4. Count how many bricks newly become connected to the top.

This works because a brick that becomes stable when added back in reverse corresponds to a brick that would have fallen when that hit happened forward.

We also add a virtual roof node.

Every brick in the top row is connected to this roof node. Then the size of the roof component tells us how many bricks are stable.

Algorithm

First, copy the grid:

working = [row[:] for row in grid]

Then apply all hits to the copy:

for r, c in hits:
    working[r][c] = 0

This gives the final grid after all hits.

Create a Union-Find over all grid cells, plus one extra node called roof.

Map a cell (r, c) to an integer id:

cell_id = r * n + c

Let:

roof = m * n

Build components from the final grid:

1. For every brick in the top row, union it with roof.
2. For every brick, union it with adjacent bricks that also exist.

Then process hits in reverse.

For each hit (r, c):

1. If grid[r][c] == 0, the original cell was empty, so append 0.
2. Otherwise, record the size of the roof component before adding the brick.
3. Add the brick back to working.
4. If it is in the top row, union it with roof.
5. Union it with every existing neighboring brick.
6. Record the size of the roof component after adding the brick.
7. The number of fallen bricks is:

max(0, after - before - 1)

We subtract 1 because the brick we added back is the brick that was directly hit. The problem does not count that brick as falling.

Finally, reverse the answers.

Correctness

After all hits are applied, working represents the grid state after the full forward process, except that fallen bricks are not explicitly simulated. This is enough for the reverse algorithm because only bricks still present after removals are included in the initial Union-Find structure.

The Union-Find structure groups adjacent bricks into connected components. The virtual roof node is connected to every top-row brick, so a brick is stable exactly when it belongs to the same component as roof.

When we process a hit backward, we restore one brick that existed in the original grid. If the original cell was empty, that hit removed nothing in the forward direction, so the correct result is 0.

Otherwise, adding the brick back may connect some previously unstable components to the roof component. The number of bricks newly connected to the roof is the increase in the roof component size.

This increase includes the restored brick itself. In the forward direction, that restored brick is the brick directly erased by the hit, so it should not be counted as falling. Therefore the number of falling bricks is after - before - 1, clipped at zero.

Every forward hit corresponds to exactly one reverse restoration, and the reverse process handles the hits in the opposite order. Thus every result computed in reverse matches the number of bricks that would fall after the corresponding forward hit.

Complexity

Let:

N = m * n

and let k be the number of hits.

Here, α(N) is the inverse Ackermann function, which grows so slowly that it is effectively constant for practical input sizes.

Implementation

class DSU:
    def __init__(self, size: int):
        self.parent = list(range(size))
        self.component_size = [1] * size

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> None:
        root_a = self.find(a)
        root_b = self.find(b)

        if root_a == root_b:
            return

        if self.component_size[root_a] < self.component_size[root_b]:
            root_a, root_b = root_b, root_a

        self.parent[root_b] = root_a
        self.component_size[root_a] += self.component_size[root_b]

    def size(self, x: int) -> int:
        return self.component_size[self.find(x)]

class Solution:
    def hitBricks(self, grid: list[list[int]], hits: list[list[int]]) -> list[int]:
        m = len(grid)
        n = len(grid[0])
        roof = m * n

        def index(r: int, c: int) -> int:
            return r * n + c

        working = [row[:] for row in grid]

        for r, c in hits:
            working[r][c] = 0

        dsu = DSU(m * n + 1)

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        for r in range(m):
            for c in range(n):
                if working[r][c] == 0:
                    continue

                if r == 0:
                    dsu.union(index(r, c), roof)

                for dr, dc in directions:
                    nr = r + dr
                    nc = c + dc

                    if 0 <= nr < m and 0 <= nc < n and working[nr][nc] == 1:
                        dsu.union(index(r, c), index(nr, nc))

        answer_reversed = []

        for r, c in reversed(hits):
            if grid[r][c] == 0:
                answer_reversed.append(0)
                continue

            before = dsu.size(roof)

            working[r][c] = 1

            if r == 0:
                dsu.union(index(r, c), roof)

            for dr, dc in directions:
                nr = r + dr
                nc = c + dc

                if 0 <= nr < m and 0 <= nc < n and working[nr][nc] == 1:
                    dsu.union(index(r, c), index(nr, nc))

            after = dsu.size(roof)

            fallen = max(0, after - before - 1)
            answer_reversed.append(fallen)

        return answer_reversed[::-1]

Code Explanation

The DSU class stores connected components.

self.parent = list(range(size))
self.component_size = [1] * size

Each node starts as its own component.

The find function returns the root of a component and applies path compression:

while self.parent[x] != x:
    self.parent[x] = self.parent[self.parent[x]]
    x = self.parent[x]

The union function merges two components:

self.parent[root_b] = root_a
self.component_size[root_a] += self.component_size[root_b]

The larger component remains the root. This keeps the tree shallow.

In the main solution, we create a virtual roof node:

roof = m * n

All real grid cells use ids from 0 to m * n - 1, so m * n is safe for the extra node.

We copy the grid:

working = [row[:] for row in grid]

Then remove all hit bricks from the copy:

for r, c in hits:
    working[r][c] = 0

This lets us build the Union-Find structure from the final state.

When building components, every top-row brick connects to the roof:

if r == 0:
    dsu.union(index(r, c), roof)

Every adjacent pair of bricks is also connected.

During reverse processing, if the original grid had no brick at the hit location, the answer is zero:

if grid[r][c] == 0:
    answer_reversed.append(0)
    continue

Otherwise, we measure the roof component size before restoration:

before = dsu.size(roof)

Then we add the brick back and union it with the roof or neighboring bricks.

After that, we measure again:

after = dsu.size(roof)

The difference tells us how many bricks newly became stable. We subtract one for the restored brick itself:

fallen = max(0, after - before - 1)

Finally, because hits were processed backward, we reverse the result:

return answer_reversed[::-1]

Testing

def run_tests():
    s = Solution()

    assert s.hitBricks(
        [[1, 0, 0, 0],
         [1, 1, 1, 0]],
        [[1, 0]]
    ) == [2]

    assert s.hitBricks(
        [[1, 0, 0, 0],
         [1, 1, 0, 0]],
        [[1, 1], [1, 0]]
    ) == [0, 0]

    assert s.hitBricks(
        [[1]],
        [[0, 0]]
    ) == [0]

    assert s.hitBricks(
        [[0]],
        [[0, 0]]
    ) == [0]

    assert s.hitBricks(
        [[1, 1, 1],
         [0, 1, 0],
         [0, 1, 0]],
        [[1, 1]]
    ) == [1]

    print("all tests passed")

run_tests()