We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Bricks Falling When Hit

Difficulty: Hard

Problem Description

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] = (row_i, col_i). 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. Return an array result, where each result[i] is the number of bricks that will fall after the i-th erasure is applied.

Key Insights

  • A brick can fall if it is not stable after a hit.
  • Stability depends on connectivity to the top or adjacent stable bricks.
  • The problem can be effectively handled using a Union-Find data structure for tracking stable bricks.

Space and Time Complexity

Time Complexity: O(hits.length * (m * n + α)) where α is the inverse Ackermann function, which is nearly constant for practical input sizes. Space Complexity: O(m * n) for the Union-Find structure and the grid.

Solution

To solve this problem, we can use the Union-Find (Disjoint Set Union) data structure to keep track of connected components of bricks. The plan is as follows:

  1. Reverse Hits: Start by initializing the grid and applying the hits in reverse order. This allows us to rebuild the grid and check the stability of bricks after each "hit".
  2. Union-Find Initialization: Create a Union-Find structure to manage which bricks are connected. Each brick will be connected to its adjacent bricks if they are stable.
  3. Stability Check: After each hit is "reversed", check which bricks are stable by connecting them to the top row or to other stable bricks.
  4. Count Falling Bricks: For each hit, after updating the stability, count how many bricks fall due to the current state of the grid.

Code Solutions

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [1] * size

    def find(self, x):
        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:
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1

def hitBricks(grid, hits):
    m, n = len(grid), len(grid[0])
    uf = UnionFind(m * n + 1)  # +1 for the virtual top
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    # Mark all hits in the grid
    for x, y in hits:
        if grid[x][y] == 1:
            grid[x][y] = 0
    
    # Rebuild the grid and union stable bricks
    for j in range(n):
        if grid[0][j] == 1:
            uf.union(j, m * n)  # Connect to virtual top
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                for di, dj in directions:
                    ni, nj = i + di, j + dj
                    if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
                        uf.union(i * n + j, ni * n + nj)

    results = []
    
    # Process hits in reverse order
    for x, y in reversed(hits):
        if grid[x][y] == 0:
            grid[x][y] = 1  # Restore the brick
            if x == 0:
                uf.union(y, m * n)  # Connect to virtual top
            for di, dj in directions:
                ni, nj = x + di, y + dj
                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
                    uf.union(x * n + y, ni * n + nj)

            # Count how many bricks fell
            count = uf.find(x * n + y) - uf.find(m * n)
            results.append(count)
        else:
            results.append(0)

    return results[::-1]  # Reverse the results to match the order of hits
← Back to All Questions