<p>You are given an <code>m x n</code> binary <code>grid</code>, where each <code>1</code> represents a brick and <code>0</code> represents an empty space. A brick is <strong>stable</strong> if:</p>

<ul>
	<li>It is directly connected to the top of the grid, or</li>
	<li>At least one other brick in its four adjacent cells is <strong>stable</strong>.</li>
</ul>

<p>You are also given an array <code>hits</code>, which is a sequence of erasures we want to apply. Each time we want to erase the brick at the location <code>hits[i] = (row<sub>i</sub>, col<sub>i</sub>)</code>. The brick on that location&nbsp;(if it exists) will disappear. Some other bricks may no longer be stable because of that erasure and will <strong>fall</strong>. Once a brick falls, it is <strong>immediately</strong> erased from the <code>grid</code> (i.e., it does not land on other stable bricks).</p>

<p>Return <em>an array </em><code>result</code><em>, where each </em><code>result[i]</code><em> is the number of bricks that will <strong>fall</strong> after the </em><code>i<sup>th</sup></code><em> erasure is applied.</em></p>

<p><strong>Note</strong> that an erasure may refer to a location with no brick, and if it does, no bricks drop.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
<strong>Output:</strong> [2]
<strong>Explanation: </strong>Starting with the grid:
[[1,0,0,0],
 [<u>1</u>,1,1,0]]
We erase the underlined brick at (1,0), resulting in the grid:
[[1,0,0,0],
 [0,<u>1</u>,<u>1</u>,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].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
<strong>Output:</strong> [0,0]
<strong>Explanation: </strong>Starting with the grid:
[[1,0,0,0],
 [1,<u>1</u>,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],
 [<u>1</u>,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].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 200</code></li>
	<li><code>grid[i][j]</code> is <code>0</code> or <code>1</code>.</li>
	<li><code>1 &lt;= hits.length &lt;= 4 * 10<sup>4</sup></code></li>
	<li><code>hits[i].length == 2</code></li>
	<li><code>0 &lt;= x<sub>i&nbsp;</sub>&lt;= m - 1</code></li>
	<li><code>0 &lt;=&nbsp;y<sub>i</sub> &lt;= n - 1</code></li>
	<li>All <code>(x<sub>i</sub>, y<sub>i</sub>)</code> are unique.</li>
</ul>

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [1] * size  # Track tree height for union by rank
        self.size = [1] * size   # Track the size of each component
    
    # Find the root of a node with path compression
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]
    
    # Union by rank to keep the tree flat
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
                self.size[rootX] += self.size[rootY]  # Merge sizes
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
                self.size[rootY] += self.size[rootX]  # Merge sizes
            else:
                self.parent[rootY] = rootX
                self.size[rootX] += self.size[rootY]
                self.rank[rootX] += 1

    # Get the size of the component containing x
    def getSize(self, x):
        return self.size[self.find(x)]

class Solution:
    def hitBricks(self, grid, hits):
        # Helper function to convert (r, c) coordinates to 1D index
        def index(r, c):
            return r * cols + c

        rows, cols = len(grid), len(grid[0])
        uf = UnionFind(rows * cols + 1)  # +1 for the "virtual top" node
        virtual_top = rows * cols  # Index for the virtual top row
        
        # Make a copy of the grid to simulate the hits
        grid_copy = [row[:] for row in grid]
        
        # Apply hits, marking the bricks to be removed
        for r, c in hits:
            grid_copy[r][c] = 0
        
        # Step 1: Union all stable bricks with their neighbors
        for r in range(rows):
            for c in range(cols):
                if grid_copy[r][c] == 1:
                    # Connect to top row if it's in the first row
                    if r == 0:
                        uf.union(index(r, c), virtual_top)
                    # Connect with left and top neighbors if they are bricks
                    if r > 0 and grid_copy[r - 1][c] == 1:
                        uf.union(index(r, c), index(r - 1, c))
                    if c > 0 and grid_copy[r][c - 1] == 1:
                        uf.union(index(r, c), index(r, c - 1))

        # Step 2: Process the hits in reverse order and count the falling bricks
        result = []
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]  # Down, Up, Right, Left

        # Traverse hits in reverse order
        for r, c in reversed(hits):
            if grid[r][c] == 0:
                # If there was no brick originally, no bricks fall, so add 0
                result.append(0)
            else:
                # Before re-adding the brick, note how many are connected to the top
                prev_top_connected_bricks = uf.getSize(virtual_top)
                
                # Add the brick back in the copy grid
                grid_copy[r][c] = 1
                
                # Reconnect this brick to its neighbors if they are bricks
                if r == 0:
                    uf.union(index(r, c), virtual_top)  # Connect to the virtual top if in the first row
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid_copy[nr][nc] == 1:
                        uf.union(index(r, c), index(nr, nc))

                # Now, count how many bricks are connected to the top after adding this one
                current_top_connected_bricks = uf.getSize(virtual_top)

                # Number of new bricks that are connected = new - previous, excluding the brick we just added
                fallen_bricks = max(0, current_top_connected_bricks - prev_top_connected_bricks - 1)
                result.append(fallen_bricks)
        
        # Since we processed the hits in reverse order, reverse the result list
        return result[::-1]

27000