> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.
> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.
# Bricks Falling When Hit Python Solution
> Tested Python solution for LeetCode 803 with 20 pytest cases. Generate a practice environment with lcpy.
LeetCode 803, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Union-Find](/catalog/topics/union-find), [Matrix](/catalog/topics/matrix). [View on LeetCode](https://leetcode.com/problems/bricks-falling-when-hit/description/).
Generate this problem as a practice environment: tested reference solution, 20 [parametrized pytest cases](/practice/testing), and a playground notebook:
```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 803 # by problem number
lcpy gen -s bricks_falling_when_hit # by problem name
```
## Problem
You are given an `m x n` binary grid, where each `1` represents a brick and `0` represents an empty space. A brick is **stable** if:
* It is directly connected to the top of the grid, or
* At least one other brick in its four adjacent cells is **stable**.
You are also given an array `hits`, which is a sequence of erasures we want to apply. Each time we want to erase the brick at the location `hits[i] = (rowi, coli)`. The brick on that location (if it exists) will disappear. Some other bricks may no longer be stable because of that erasure and will **fall**. Once a brick falls, it is immediately erased from the grid (i.e., it does not land on other stable bricks).
Return an array `result`, where each `result[i]` is the number of bricks that will fall after the `ith` erasure is applied.
**Note** that an erasure may refer to a location with no brick, and if it does, no bricks drop.
### Examples
```
Input: grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
Output: [2]
Explanation: Starting with the grid:
[[1,0,0,0],
[1,1,1,0]]
We erase the brick at (1,0), resulting in the grid:
[[1,0,0,0],
[0,1,1,0]]
The two bricks are no longer stable as they are no longer connected to the top nor adjacent to another stable brick, so they will fall. The resulting grid is:
[[1,0,0,0],
[0,0,0,0]]
Hence the result is [2].
```
```
Input: grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
Output: [0,0]
Explanation: Starting with the grid:
[[1,0,0,0],
[1,1,0,0]]
We erase the brick at (1,1), resulting in the grid:
[[1,0,0,0],
[1,0,0,0]]
All remaining bricks are still stable, so no bricks fall. Next, we erase the brick at (1,0), resulting in the grid:
[[1,0,0,0],
[0,0,0,0]]
Once again, all remaining bricks are still stable, so no bricks fall.
Hence the result is [0,0].
```
### Constraints
* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 200`
* `grid[i][j]` is `0` or `1`.
* `1 <= hits.length <= 4 * 10^4`
* `hits[i].length == 2`
* `0 <= x_i <= m - 1`
* `0 <= y_i <= n - 1`
* All `(x_i, y_i)` are unique.
## Solution
Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/bricks_falling_when_hit/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/bricks_falling_when_hit/test_solution.py):
```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
# Time: O(rows * cols + len(hits) * alpha(rows * cols))
# Space: O(rows * cols)
def hit_bricks(self, grid: list[list[int]], hits: list[list[int]]) -> list[int]:
rows, cols = len(grid), len(grid[0])
# Work on a grid with every hit brick already erased, then re-add them in
# reverse: erasures are hard to undo, additions are just unions.
remaining = [row[:] for row in grid]
for row, col in hits:
remaining[row][col] = 0
top = rows * cols
parent = list(range(top + 1))
size = [1] * (top + 1)
def find(node: int) -> int:
while parent[node] != node:
parent[node] = parent[parent[node]]
node = parent[node]
return node
def union(left: int, right: int) -> None:
root_left, root_right = find(left), find(right)
if root_left == root_right:
return
if size[root_left] < size[root_right]:
root_left, root_right = root_right, root_left
parent[root_right] = root_left
size[root_left] += size[root_right]
def stable_bricks() -> int:
# Bricks attached to the virtual top node (the node itself adds 1).
return size[find(top)] - 1
def add_brick(row: int, col: int) -> None:
node = row * cols + col
if row == 0:
union(node, top)
for d_row, d_col in ((1, 0), (-1, 0), (0, 1), (0, -1)):
n_row, n_col = row + d_row, col + d_col
if 0 <= n_row < rows and 0 <= n_col < cols and remaining[n_row][n_col]:
union(node, n_row * cols + n_col)
for row in range(rows):
for col in range(cols):
if remaining[row][col]:
add_brick(row, col)
results: list[int] = []
for row, col in reversed(hits):
if grid[row][col] == 0:
results.append(0) # erasure on an empty cell, nothing drops
continue
before = stable_bricks()
add_brick(row, col)
remaining[row][col] = 1
after = stable_bricks()
# Re-adding the hit brick itself accounts for one of the newcomers.
results.append(max(0, after - before - 1))
results.reverse()
return results
```
## Complexity
| Time | Space |
| - | - |
| O(rows \* cols + len(hits) \* alpha(rows \* cols)) | O(rows \* cols) |
## Tags
This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.