How do I solve Bricks Falling When Hit using Union Find?

You need to simulate the erasure of bricks while tracking the stability of others using Union Find. Start by reversing the hits and restoring the grid before applying each hit.

What is the time complexity of the Bricks Falling When Hit problem?

The time complexity is O(N * α(N)), where N is the number of cells in the grid and α(N) is the inverse Ackermann function.

How can I handle multiple hits in the Bricks Falling When Hit problem?

You can process the hits in reverse order, restoring the grid at each step, and then using Union Find to determine the number of falling bricks after each hit.

What happens if a brick is no longer stable after a hit?

If a brick is no longer stable after a hit, it falls and is erased from the grid immediately, affecting the stability of other connected bricks.

How does GhostInterview assist with solving Bricks Falling When Hit?

GhostInterview offers real-time feedback and helps you optimize your Union Find approach, providing detailed explanations to avoid common pitfalls and improve your solution.

#803

Hard

auto_awesome并查集

LeetCode 题解工作台

打砖块

有一个 m x n 的二元网格 grid ，其中 1 表示砖块， 0 表示空白。砖块稳定（不会掉落）的前提是：一块砖直接连接到网格的顶部，或者至少有一块相邻（4 个方向之一）砖块稳定不会掉落时给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi…

数组并查集矩阵

题目描述

有一个 m x n 的二元网格 grid ，其中 1 表示砖块，0 表示空白。砖块稳定（不会掉落）的前提是：

一块砖直接连接到网格的顶部，或者
至少有一块相邻（4 个方向之一）砖块稳定不会掉落时

给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而掉落。一旦砖块掉落，它会立即从网格 grid 中消失（即，它不会落在其他稳定的砖块上）。

返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。

注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。

示例 1：

输入：grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
输出：[2]
解释：网格开始为：
[[1,0,0,0]，
 [1,1,1,0]]
消除 (1,0) 处加粗的砖块，得到网格：
[[1,0,0,0]
 [0,1,1,0]]
两个加粗的砖不再稳定，因为它们不再与顶部相连，也不再与另一个稳定的砖相邻，因此它们将掉落。得到网格：
[[1,0,0,0],
 [0,0,0,0]]
因此，结果为 [2] 。

示例 2：

输入：grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
输出：[0,0]
解释：网格开始为：
[[1,0,0,0],
 [1,1,0,0]]
消除 (1,1) 处加粗的砖块，得到网格：
[[1,0,0,0],
 [1,0,0,0]]
剩下的砖都很稳定，所以不会掉落。网格保持不变：
[[1,0,0,0], 
 [1,0,0,0]]
接下来消除 (1,0) 处加粗的砖块，得到网格：
[[1,0,0,0],
 [0,0,0,0]]
剩下的砖块仍然是稳定的，所以不会有砖块掉落。
因此，结果为 [0,0] 。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
grid[i][j] 为 0 或 1
1 <= hits.length <= 4 * 10⁴
hits[i].length == 2
0 <= x_i<= m - 1
0 <= y_i <= n - 1
所有 (x_i, y_i) 互不相同

lightbulb

解题思路

方法一

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

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]

speed

复杂度分析

指标	值
时间	O(N \cdot \alpha(N))
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Tests the candidate's ability to handle grid manipulation using efficient data structures like Union Find.
question_mark
Assesses the candidate's understanding of graph connectivity and the impact of sequential modifications on data structures.
question_mark
Evaluates the candidate's approach to problem-solving under constraints like time complexity and handling large inputs.

warning

常见陷阱

外企场景

error
Forgetting to reverse the hits and restoring the grid before processing each hit.
error
Mismanaging the Union Find structure, leading to incorrect connectivity checks.
error
Overcomplicating the problem by using brute force instead of efficient Union Find operations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the grid was dynamic and cells could be added after each erasure?
arrow_right_alt
How would you approach this if you were required to support a 3D grid?
arrow_right_alt
Can this be optimized further for very large grids, say for a billion cells?

help

常见问题

外企场景

继续练习

#827 最大人工岛 #778 水位上升的泳池中游泳 #695 岛屿的最大面积