# LeetCode 803: Bricks Falling When Hit

## Problem Restatement

We are given an `m x n` grid.

Each cell is either:

| Value | Meaning |
|---|---|
| `1` | Brick |
| `0` | Empty space |

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

| Item | Meaning |
|---|---|
| Input | A binary grid `grid` and a list of hit positions `hits` |
| Output | Number of falling bricks after each hit |
| Stable brick | A brick connected to the top row |
| Falling brick | A brick that loses connection to the top row |
| Important detail | The erased brick itself is not counted as falling |

## Examples

Example 1:

```python
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:

```python
[2]
```

Example 2:

```python
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:

```python
[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:

```python
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:

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

Then apply all hits to the copy:

```python
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:

```python
cell_id = r * n + c
```

Let:

```python
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:

```python
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:

```python
N = m * n
```

and let `k` be the number of hits.

| Metric | Value | Why |
|---|---|---|
| Time | `O((N + k) α(N))` | Union-Find operations are nearly constant time |
| Space | `O(N)` | Parent array, size array, and copied grid |

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

## Implementation

```python
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.

```python
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:

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

The `union` function merges two components:

```python
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:

```python
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:

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

Then remove all hit bricks from the copy:

```python
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:

```python
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:

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

Otherwise, we measure the roof component size before restoration:

```python
before = dsu.size(roof)
```

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

After that, we measure again:

```python
after = dsu.size(roof)
```

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

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

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

```python
return answer_reversed[::-1]
```

## Testing

```python
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()
```

| Test | Why |
|---|---|
| Sample with falling chain | Counts bricks disconnected from the roof |
| Sequential hits | Checks that later hits see earlier removals |
| Single brick | Hit brick itself is not counted |
| Empty cell hit | No brick removed, no fall |
| Vertical support removal | Checks reverse restoration and roof-size difference |