LeetCode Solutions Blog

Bricks Falling When Hit

Number: 821

Difficulty: Hard

Paid? No

Problem Description

Given an m x n grid with bricks (1 represents a brick, 0 represents an empty space), a brick is considered stable if it is connected directly to the top row or connected (vertically or horizontally) to another stable brick. We are given an array of hit operations (each hit erases a possible brick). After each hit, some bricks may lose connectivity and fall (i.e. be removed). The problem asks to return an array where each element is the number of bricks that fall as a result of the corresponding hit.

Key Insights

Instead of processing hits in the forward order (which leads to complex dependency chains), process the hits in reverse order.
Remove all bricks corresponding to hits initially and build the connected components (using Union Find) for the remaining grid.
Introduce a special "roof" node to represent the stability provided by the top row.
In the reverse process, restore one brick at a time and union it with adjacent bricks. The increase in the number of bricks connected to the roof indicates how many bricks become stable.
The brick being restored is not counted as "fallen" so subtract one from the increase.

Space and Time Complexity

Time Complexity: O(mn + k * α(mn)) where mn is the size of the grid, k is the number of hits, and α is the inverse Ackermann function (almost constant). Space Complexity: O(mn) for the Union Find data structure and auxiliary arrays.

Solution

We solve this problem by using a Union Find (Disjoint Set Union) data structure with a twist. First, we simulate all hits by marking the bricks as removed. Then, we build the union structure for the remaining grid while uniting adjacent bricks. A virtual roof node is used to represent stability from the top row. After the initial setup, we process hits in reverse order. For every hit that originally removed a brick, we add the brick back and connect it to its neighbors if they exist. By checking the difference in the size of the connected component at the roof node before and after the restoration, we determine how many bricks become stable due to this brick and hence would not have fallen if the hit had not occurred. Since the brick we restore should not be counted, we subtract one from that difference. This reverse approach transforms the problem into several union operations and gives an efficient solution.

Code Solutions

# Python solution using Union Find

class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        # Size array to hold the component size (number of nodes)
        self.size = [1] * size

    def find(self, x):
        # Path compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return 0  # They are already in the same set
        # Attach smaller tree under larger tree's root
        if self.size[rootX] < self.size[rootY]:
            self.parent[rootX] = rootY
            self.size[rootY] += self.size[rootX]
            return self.size[rootX]
        else:
            self.parent[rootY] = rootX
            self.size[rootX] += self.size[rootY]
            return self.size[rootY]

    def getSize(self, x):
        root = self.find(x)
        return self.size[root]

def hitBricks(grid, hits):
    m, n = len(grid), len(grid[0])
    size = m * n
    # the roof node is at index size
    roof = size
    uf = UnionFind(size + 1)

    def index(i, j):
        return i * n + j

    # Copy grid and mark hits
    grid_copy = [row[:] for row in grid]
    for i, j in hits:
        # Mark the brick as removed if it exists
        if grid_copy[i][j] == 1:
            grid_copy[i][j] = 0

    # Initial union for remaining bricks after all hits:
    # Connect brick in top row directly with roof
    for i in range(m):
        for j in range(n):
            if grid_copy[i][j] == 1:
                if i == 0:
                    uf.union(index(i, j), roof)
                # union with adjacent bricks (only up and left to avoid duplicates)
                for dx, dy in [(-1, 0), (0, -1)]:
                    ni, nj = i + dx, j + dy
                    if 0 <= ni < m and 0 <= nj < n and grid_copy[ni][nj] == 1:
                        uf.union(index(i, j), index(ni, nj))

    res = [0] * len(hits)
    # Process hits in reverse
    for k in range(len(hits) - 1, -1, -1):
        i, j = hits[k]
        # if there was no brick originally, nothing to add
        if grid[i][j] == 0:
            continue
        preRoofConnected = uf.getSize(roof)
        # Add back the brick
        grid_copy[i][j] = 1
        # If the brick is in the first row, connect it to the roof
        if i == 0:
            uf.union(index(i, j), roof)
        # union with adjacent bricks
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            ni, nj = i + dx, j + dy
            if 0 <= ni < m and 0 <= nj < n and grid_copy[ni][nj] == 1:
                uf.union(index(i, j), index(ni, nj))
        postRoofConnected = uf.getSize(roof)
        # new connections are bricks that have become stable
        # subtract one since the brick added back is not counted
        fallen = max(0, postRoofConnected - preRoofConnected - 1)
        res[k] = fallen
    return res

# Example usage:
grid = [[1,0,0,0],[1,1,1,0]]
hits = [[1,0]]
print(hitBricks(grid, hits))  # Expected output: [2]