{x}
blog image

Bricks Falling When Hit

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.

Solution Explanation for LeetCode 803: Bricks Falling When Hit

This problem requires determining how many bricks fall after each hit in a grid. We'll use a Union-Find algorithm for efficient tracking of connected components.

Approach:

  1. Reverse Iteration: We process the hits in reverse order. This simplifies the logic because we only need to consider the addition of a brick, not its removal.

  2. Union-Find: We maintain a Union-Find data structure to track connected components of stable bricks. Each brick is represented by a node in the Union-Find. The root of the connected component represents the stability of those bricks. A special node (m * n) represents the top of the grid. Any brick connected to the top is considered stable.

  3. Initial Setup: Initially, we simulate the grid after all hits. We perform union operations on the initial grid to determine connected components and the size of each component.

  4. Iterative Hit Processing (Reverse): For each hit in reverse order:

    • If the hit location is already empty (0), we move to the next hit.
    • Otherwise, we "restore" the brick at that location.
    • We perform union operations with adjacent stable bricks (if any).
    • We calculate the difference in the size of the connected component containing the top of the grid before and after the union operations. This difference (minus 1 to account for the newly restored brick) represents the number of bricks that fell.

Time Complexity:

  • The initialization step takes O(m*n) time.
  • The reverse iteration and union operations in each step take, in the worst case, O(m*n) time. Since we perform this for each hit, the total time is O(hits.length * m * n).

Space Complexity:

  • The space complexity is O(m*n) due to the Union-Find data structure (p and size arrays), grid copy, and other auxiliary arrays.

Code Implementation (Python):

class Solution:
    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
        m, n = len(grid), len(grid[0])
        p = list(range(m * n + 1))  # Union-Find parent array; m*n is a special node for top
        size = [1] * (m * n + 1)    # Size of each connected component
 
        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
 
        # Simulate the grid after all hits
        g = deepcopy(grid)
        for r, c in hits:
            g[r][c] = 0
 
        # Initial Union-Find setup
        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] == 1:
                    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 r, c in hits[::-1]: # Process hits in reverse
            if grid[r][c] == 0:
                ans.append(0)
                continue
            g[r][c] = 1
            prev_size = size[find(m * n)]
            if r == 0:
                union(c, m * n)
            else:
                for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < m and 0 <= nc < n and g[nr][nc] == 1:
                        union(r * n + c, nr * n + nc)
            ans.append(max(0, size[find(m * n)] - prev_size -1)) #Account for the newly added brick
        return ans[::-1]

The other language implementations (Java, C++, Go) follow the same algorithm and have similar time and space complexity. The core idea is the reverse iteration and the clever use of Union-Find to efficiently track the stability of bricks.