# Bricks Falling When Hit
**Difficulty:** HARD
[External](https://leetcode.com/problems/bricks-falling-when-hit)
Canonical: https://scaleengineer.com/dsa/problems/bricks-falling-when-hit
**Algorithms:** [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Matrix
**Companies:** [Snap](https://scaleengineer.com/companies/snap), [Tower Research Capital](https://scaleengineer.com/companies/tower-research-capital)
---
## 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.

**Example 1:**

**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 underlined brick at (1,0), resulting in the grid:
[[1,0,0,0],
 [0,1,1,0]]
The two underlined 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].

**Example 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 underlined 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. The grid remains the same:
[[1,0,0,0],
 [1,0,0,0]]
Next, we erase the underlined 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 * 104`
* `hits[i].length == 2`
* `0 <= xi <= m - 1`
* `0 <= yi <= n - 1`
* All `(xi, yi)` are unique.

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem. For each hit, it removes the specified brick and then re-evaluates the stability of all remaining bricks from scratch by performing a full grid traversal. This is the most straightforward but also the least efficient method.
**Time:** O(K * M * N), where K is the number of hits, and M and N are the dimensions of the grid. For each of the K hits, we may traverse the entire grid, leading to a complexity of O(M * N) per hit. · **Space:** O(M * N), where M and N are the dimensions of the grid. This space is used for the `stable` boolean grid and for the recursion stack in the case of DFS.
**Pros:** Simple to understand and implement as it directly models the problem statement.
**Cons:** Highly inefficient due to its time complexity.; Will result in a 'Time Limit Exceeded' error for larger inputs as it recomputes the stability of the entire grid for every single hit.
### Explanation
The brute-force method iterates through each hit one by one. For each hit, it first updates the grid by removing the brick at the specified location. Then, it determines the consequences of this removal. To do this, it must find the new set of stable bricks. A brick is stable if it's connected to the top row. We can identify all stable bricks by starting a graph traversal (like DFS or BFS) from every brick in the top row and marking all reachable bricks. After identifying the stable bricks, any remaining brick in the grid is considered unstable and falls. We count these fallen bricks, add the count to our result, and permanently remove them from the grid to set up the state for the next hit. This entire process is repeated for every hit in the input array.

```java
class Solution {
    public int[] hitBricks(int[][] grid, int[][] hits) {
        int m = grid.length;
        int n = grid[0].length;
        int[] result = new int[hits.length];

        for (int i = 0; i < hits.length; i++) {
            int r = hits[i][0];
            int c = hits[i][1];

            if (grid[r][c] == 0) {
                result[i] = 0;
                continue;
            }

            grid[r][c] = 0; // Perform the hit

            // Find all stable bricks after the hit
            boolean[][] stable = new boolean[m][n];
            for (int j = 0; j < n; j++) {
                if (grid[0][j] == 1) {
                    dfs(0, j, grid, stable);
                }
            }

            // Count fallen bricks and update the grid
            int fallen = 0;
            for (int row = 0; row < m; row++) {
                for (int col = 0; col < n; col++) {
                    if (grid[row][col] == 1 && !stable[row][col]) {
                        fallen++;
                        grid[row][col] = 0; // Remove fallen brick for next iteration
                    }
                }
            }
            result[i] = fallen;
        }
        return result;
    }

    private void dfs(int r, int c, int[][] grid, boolean[][] stable) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 0 || stable[r][c]) {
            return;
        }
        stable[r][c] = true;
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        for (int i = 0; i < 4; i++) {
            dfs(r + dr[i], c + dc[i], grid, stable);
        }
    }
}
```
### Algorithm
*   Initialize an empty `result` array to store the number of fallen bricks for each hit.
*   Iterate through each `hit` in the `hits` array.
*   Let `(r, c)` be the coordinates of the current hit.
*   If the cell `grid[r][c]` is already empty (0), it means the hit has no effect. Add 0 to the `result` and continue to the next hit.
*   If there is a brick at `(r, c)`, perform the hit by setting `grid[r][c] = 0`.
*   After the hit, we need to identify all bricks that are no longer stable and have fallen.
    *   Create a `stable` boolean grid of the same dimensions, initialized to `false`.
    *   Start a graph traversal (like DFS or BFS) from every brick in the top row (`grid[0][j] == 1`).
    *   During the traversal, mark all reachable bricks as `true` in the `stable` grid.
*   Now, count the fallen bricks.
    *   Initialize a `fallen_count` to 0.
    *   Iterate through the entire grid. Any cell `(i, j)` that contains a brick (`grid[i][j] == 1`) but is not marked as stable (`stable[i][j] == false`) is a fallen brick.
    *   Increment `fallen_count` for each such brick.
    *   To ensure the grid state is correct for the next hit, permanently remove these fallen bricks by setting `grid[i][j] = 0`.
*   Add the `fallen_count` to the `result` array.
*   After iterating through all hits, return the `result` array.

## Reverse Time with Union-Find
This highly efficient approach avoids the costly re-computation of the brute-force method by reversing the problem. Instead of removing bricks and calculating disconnections, we start with the final state (after all hits) and add bricks back one by one in the reverse order of hits. The Union-Find data structure is perfectly suited for this, as it can efficiently track the merging of connected components and their sizes.
**Time:** O((M*N + K) * α(M*N)), where α is the extremely slow-growing Inverse Ackermann function. This is effectively linear time, O(M*N + K), making it very fast. · **Space:** O(M * N) for the Union-Find data structure's parent and size arrays. The input grid is modified in-place.
**Pros:** Very efficient, with a near-linear time complexity.; A standard and powerful technique for dynamic connectivity problems that involve removals.
**Cons:** More complex to conceptualize and implement compared to the brute-force approach.; The reverse-time logic can be counter-intuitive.
### Explanation
The core insight is that tracking connections (union) is much easier than tracking disconnections (splitting). We can simulate the process in reverse time.

First, we determine the final state of the grid after all hits have occurred. We do this by marking all bricks that will be hit. Then, we initialize a Union-Find data structure representing the grid cells plus a special 'ceiling' node. We build the initial set of connections by uniting all the bricks that survive all the hits. Bricks in the top row are united with the ceiling node, making them stable.

Next, we iterate through the `hits` array in reverse. For each hit, we 'add' the brick back to the grid. Before adding it, we query the DSU for the current number of stable bricks (the size of the component connected to the ceiling). After adding the brick back (by setting its value to 1 and uniting it with its neighbors and potentially the ceiling), we query the number of stable bricks again. The increase in the stable brick count (minus 1 for the brick we just added) represents the number of other bricks that became stable due to this addition. These are precisely the bricks that must have fallen when this brick was hit in the forward direction. We record this number and proceed to the next hit in reverse, until all hits are processed.

```java
class Solution {
    private int[] parent;
    private int[] sz; // size of component
    private int m, n;
    private int[][] grid;
    private int[] dr = {0, 1, 0, -1};
    private int[] dc = {1, 0, -1, 0};

    public int[] hitBricks(int[][] grid, int[][] hits) {
        this.m = grid.length;
        this.n = grid[0].length;
        this.grid = grid;
        int k = hits.length;
        int[] ans = new int[k];

        // Step 1: Mark bricks that will be hit.
        for (int[] hit : hits) {
            if (grid[hit[0]][hit[1]] == 1) {
                grid[hit[0]][hit[1]] = 2; // Mark as a brick to be hit
            }
        }

        // Step 2: Initialize DSU.
        int ceiling = m * n;
        parent = new int[m * n + 1];
        sz = new int[m * n + 1];
        for (int i = 0; i < m * n; i++) {
            parent[i] = i;
            sz[i] = 1;
        }
        parent[ceiling] = ceiling;
        sz[ceiling] = 0; // Ceiling node itself is not a brick

        // Step 3: Build initial connections from non-hit bricks.
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 1) {
                    unionNeighbors(r, c);
                }
            }
        }

        // Step 4: Process hits in reverse.
        for (int i = k - 1; i >= 0; i--) {
            int r = hits[i][0];
            int c = hits[i][1];

            if (grid[r][c] != 2) {
                ans[i] = 0;
            } else {
                int stableBefore = sz[find(ceiling)];
                grid[r][c] = 1; // Add the brick back
                unionNeighbors(r, c);
                int stableAfter = sz[find(ceiling)];
                ans[i] = Math.max(0, stableAfter - stableBefore - 1);
            }
        }
        return ans;
    }

    private void unionNeighbors(int r, int c) {
        int idx = r * n + c;
        if (r == 0) {
            union(idx, m * n);
        }
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
                union(idx, nr * n + nc);
            }
        }
    }

    private int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }

    private void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            if (sz[rootI] < sz[rootJ]) { // Union by size
                int temp = rootI;
                rootI = rootJ;
                rootJ = temp;
            }
            parent[rootJ] = rootI;
            sz[rootI] += sz[rootJ];
        }
    }
}
```
### Algorithm
*   **Step 1: Mark Hits & Prepare Initial State.**
    *   Modify the input `grid` in-place. Iterate through the `hits` array. If a hit `(r, c)` is on a brick (`grid[r][c] == 1`), change its value to 2. This marks it as a brick that will be hit later.
    *   The initial state for our reverse process is a grid containing only the bricks that are *never* hit (value 1).
*   **Step 2: Initialize Union-Find.**
    *   Create a Union-Find (DSU) data structure with `M*N + 1` elements. The elements `0` to `M*N - 1` correspond to the grid cells, and the extra element `M*N` acts as a virtual 'ceiling' node, representing the source of stability.
    *   Initialize the `size` array such that `size[i] = 1` for grid cells and `size[ceiling] = 0`.
*   **Step 3: Build Initial Connections.**
    *   Iterate through the grid. For every brick that was never hit (`grid[r][c] == 1`), connect it to its adjacent non-hit bricks using the `union` operation. 
    *   If a non-hit brick is in the top row (`r == 0`), union it with the ceiling node `M*N`.
    *   After this step, `size[find(ceiling)]` gives the number of stable bricks *after all hits have occurred*.
*   **Step 4: Process Hits in Reverse.**
    *   Create a `result` array. Iterate through the `hits` array backwards (from `k-1` to `0`).
    *   For each hit `(r, c)`:
        *   If `grid[r][c]` is not 2, it means the hit was on an empty space or a brick that was already removed by a previous hit in the original sequence. The number of fallen bricks is 0. Store this and continue.
        *   If `grid[r][c] == 2`, we are 'adding' this brick back.
        *   First, record the number of stable bricks *before* adding it back: `stable_before = size[find(ceiling)]`.
        *   Change `grid[r][c]` from 2 to 1, effectively adding it to the grid.
        *   Union the newly added brick with all its adjacent neighbors (that are now bricks) and with the ceiling node if it's in the top row.
        *   After the unions, find the new count of stable bricks: `stable_after = size[find(ceiling)]`.
        *   The number of bricks that just became stable by adding this brick is `stable_after - stable_before - 1`. The `-1` accounts for the hit brick itself. This is the number of bricks that fell. Store `max(0, stable_after - stable_before - 1)` in the result.
*   **Step 5: Return Result.**
    *   The `result` array is filled in reverse order, so it's already correct. Return it.

# Solutions
### Java

```java
class Solution {
private
  int[] p;
private
  int[] size;
public
  int[] hitBricks(int[][] grid, int[][] hits) {
    int m = grid.length;
    int n = grid[0].length;
    p = new int[m * n + 1];
    size = new int[m * n + 1];
    for (int i = 0; i < p.length; ++i) {
      p[i] = i;
      size[i] = 1;
    }
    int[][] g = new int[m][n];
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        g[i][j] = grid[i][j];
      }
    }
    for (int[] h : hits) {
      g[h[0]][h[1]] = 0;
    }
    for (int j = 0; j < n; ++j) {
      if (g[0][j] == 1) {
        union(j, m * n);
      }
    }
    for (int i = 1; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (g[i][j] == 0) {
          continue;
        }
        if (g[i - 1][j] == 1) {
          union(i * n + j, (i - 1) * n + j);
        }
        if (j > 0 && g[i][j - 1] == 1) {
          union(i * n + j, i * n + j - 1);
        }
      }
    }
    int[] ans = new int[hits.length];
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int k = hits.length - 1; k >= 0; --k) {
      int i = hits[k][0];
      int j = hits[k][1];
      if (grid[i][j] == 0) {
        continue;
      }
      g[i][j] = 1;
      int prev = size[find(m * n)];
      if (i == 0) {
        union(j, m * n);
      }
      for (int l = 0; l < 4; ++l) {
        int x = i + dirs[l];
        int y = j + dirs[l + 1];
        if (x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 1) {
          union(i * n + j, x * n + y);
        }
      }
      int curr = size[find(m * n)];
      ans[k] = Math.max(0, curr - prev - 1);
    }
    return ans;
  }
private
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
private
  void union(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    if (pa != pb) {
      size[pb] += size[pa];
      p[pa] = pb;
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> p;
  vector<int> size;
  vector<int> hitBricks(vector<vector<int>> &grid, vector<vector<int>> &hits) {
    int m = grid.size(), n = grid[0].size();
    p.resize(m * n + 1);
    size.resize(m * n + 1);
    for (int i = 0; i < p.size(); ++i) {
      p[i] = i;
      size[i] = 1;
    }
    vector<vector<int>> g(m, vector<int>(n));
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        g[i][j] = grid[i][j];
    for (auto &h : hits)
      g[h[0]][h[1]] = 0;
    for (int j = 0; j < n; ++j)
      if (g[0][j] == 1)
        merge(j, m * n);
    for (int i = 1; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (g[i][j] == 0)
          continue;
        if (g[i - 1][j] == 1)
          merge(i * n + j, (i - 1) * n + j);
        if (j > 0 && g[i][j - 1] == 1)
          merge(i * n + j, i * n + j - 1);
      }
    }
    vector<int> ans(hits.size());
    vector<int> dirs = {-1, 0, 1, 0, -1};
    for (int k = hits.size() - 1; k >= 0; --k) {
      int i = hits[k][0], j = hits[k][1];
      if (grid[i][j] == 0)
        continue;
      g[i][j] = 1;
      int prev = size[find(m * n)];
      if (i == 0)
        merge(j, m * n);
      for (int l = 0; l < 4; ++l) {
        int x = i + dirs[l], y = j + dirs[l + 1];
        if (x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 1)
          merge(i * n + j, x * n + y);
      }
      int curr = size[find(m * n)];
      ans[k] = max(0, curr - prev - 1);
    }
    return ans;
  }
  int find(int x) {
    if (p[x] != x)
      p[x] = find(p[x]);
    return p[x];
  }
  void merge(int a, int b) {
    int pa = find(a), pb = find(b);
    if (pa != pb) {
      size[pb] += size[pa];
      p[pa] = pb;
    }
  }
};

```

### Python

```python
class Solution:
    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] def union(a, b): pa, pb = find(a), find(b) if pa != pb: size[pb] += size[pa] p[pa] = pb m, n = len(grid), len(grid[0]) p = list(range(m * n + 1)) size = [1] * len(p) g = deepcopy(grid) for i, j in hits: g[i][j] = 0 for j in range(n): if g[0][j] == 1: union(j, m * n) for i in range(1, m): for j in range(n): if g[i][j] == 0: continue if g[i - 1][j] == 1: union(i * n + j, (i - 1) * n + j) if j > 0 and g[i][j - 1] == 1: union(i * n + j, i * n + j - 1) ans = [] for i, j in hits[:: - 1]: if grid[i][j] == 0: ans . append(0) continue g[i][j] = 1 prev = size[find(m * n)] if i == 0: union(j, m * n) 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)] ans . append(max(0, curr - prev - 1)) return ans[:: - 1]

```