Problem

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 arrayresult , where eachresult[i]_is the number of bricks that willfall 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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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 * 10^4
  • hits[i].length == 2
  • 0 <= xi <= m - 1
  • 0 <= yi <= n - 1
  • All (xi, yi) are unique.

Solution

Method 1 – Reverse Union-Find (Disjoint Set Union)

Intuition

Instead of simulating each hit forward, we process the hits in reverse. We first remove all bricks that will be hit, then add them back one by one, using Union-Find to track which bricks are connected to the top. The difference in the number of stable bricks before and after each addition gives the number of bricks that fall.

Approach

  1. Copy the grid and remove all bricks at hit positions.
  2. Use Union-Find to connect all remaining bricks, and connect bricks in the top row to a virtual top node.
  3. Process hits in reverse:
    • If the hit was on a brick, add it back.
    • Union it with its neighbors if they are bricks.
    • If it is in the top row, union it with the virtual top.
    • The number of new bricks connected to the top (excluding the added one) is the answer for this hit.
  4. Return the result in the original order.

Code

 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

class Solution {
public:
    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> g = grid;
        for (auto& h : hits) if (g[h[0]][h[1]] == 1) g[h[0]][h[1]] = 2; else g[h[0]][h[1]] = 0;
        vector<int> p(m*n+1), sz(m*n+1, 1);
        iota(p.begin(), p.end(), 0);
        auto find = [&](int x) { while (x != p[x]) x = p[x] = p[p[x]]; return x; };
        auto unite = [&](int x, int y) { x = find(x); y = find(y); if (x != y) { p[x] = y; sz[y] += sz[x]; } };
        int top = m*n;
        auto idx = [&](int i, int j) { return i*n+j; };
        for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (g[i][j] == 1) {
            if (i == 0) unite(idx(i,j), top);
            for (auto [di, dj] : vector<pair<int,int>>{{-1,0},{1,0},{0,-1},{0,1}}) {
                int ni = i+di, nj = j+dj;
                if (ni>=0 && ni<m && nj>=0 && nj<n && g[ni][nj]==1) unite(idx(i,j), idx(ni,nj));
            }
        }
        vector<int> ans(hits.size());
        for (int k = hits.size()-1; k >= 0; --k) {
            int i = hits[k][0], j = hits[k][1];
            if (grid[i][j] == 0) continue;
            g[i][j] = 1;
            int pre = sz[find(top)];
            for (auto [di, dj] : vector<pair<int,int>>{{-1,0},{1,0},{0,-1},{0,1}}) {
                int ni = i+di, nj = j+dj;
                if (ni>=0 && ni<m && nj>=0 && nj<n && g[ni][nj]==1) unite(idx(i,j), idx(ni,nj));
            }
            if (i == 0) unite(idx(i,j), top);
            int post = sz[find(top)];
            ans[k] = max(0, post-pre-1);
        }
        return ans;
    }
};
 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
48
49
50
51
52

func hitBricks(grid [][]int, hits [][]int) []int {
    m, n := len(grid), len(grid[0])
    g := make([][]int, m)
    for i := range g {
        g[i] = append([]int(nil), grid[i]...)
    }
    for _, h := range hits {
        if g[h[0]][h[1]] == 1 {
            g[h[0]][h[1]] = 2
        } else {
            g[h[0]][h[1]] = 0
        }
    }
    p := make([]int, m*n+1)
    sz := make([]int, m*n+1)
    for i := range p { p[i] = i; sz[i] = 1 }
    find := func(x int) int { for x != p[x] { p[x] = p[p[x]]; x = p[x] }; return x }
    unite := func(x, y int) { x, y = find(x), find(y); if x != y { p[x] = y; sz[y] += sz[x] } }
    top := m*n
    idx := func(i, j int) int { return i*n+j }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if g[i][j] == 1 {
                if i == 0 { unite(idx(i,j), top) }
                for _, d := range [][2]int{{-1,0},{1,0},{0,-1},{0,1}} {
                    ni, nj := i+d[0], j+d[1]
                    if ni>=0 && ni<m && nj>=0 && nj<n && g[ni][nj]==1 {
                        unite(idx(i,j), idx(ni,nj))
                    }
                }
            }
        }
    }
    ans := make([]int, len(hits))
    for k := len(hits)-1; k >= 0; k-- {
        i, j := hits[k][0], hits[k][1]
        if grid[i][j] == 0 { continue }
        g[i][j] = 1
        pre := sz[find(top)]
        for _, d := range [][2]int{{-1,0},{1,0},{0,-1},{0,1}} {
            ni, nj := i+d[0], j+d[1]
            if ni>=0 && ni<m && nj>=0 && nj<n && g[ni][nj]==1 {
                unite(idx(i,j), idx(ni,nj))
            }
        }
        if i == 0 { unite(idx(i,j), top) }
        post := sz[find(top)]
        ans[k] = max(0, post-pre-1)
    }
    return ans
}
func max(a, b int) int { if a > b { return a }; return b }
 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

class Solution {
    public int[] hitBricks(int[][] grid, int[][] hits) {
        int m = grid.length, n = grid[0].length;
        int[][] g = new int[m][n];
        for (int i = 0; i < m; i++) g[i] = grid[i].clone();
        for (int[] h : hits) g[h[0]][h[1]] = g[h[0]][h[1]] == 1 ? 2 : 0;
        int[] p = new int[m*n+1], sz = new int[m*n+1];
        for (int i = 0; i <= m*n; i++) { p[i] = i; sz[i] = 1; }
        int top = m*n;
        java.util.function.IntUnaryOperator find = new java.util.function.IntUnaryOperator() {
            public int applyAsInt(int x) { while (x != p[x]) x = p[x] = p[p[x]]; return x; }
        };
        java.util.function.BiConsumer<Integer, Integer> unite = (x, y) -> {
            x = find.applyAsInt(x); y = find.applyAsInt(y);
            if (x != y) { p[x] = y; sz[y] += sz[x]; }
        };
        java.util.function.IntBinaryOperator idx = (i, j) -> i*n+j;
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (g[i][j] == 1) {
            if (i == 0) unite.accept(idx.applyAsInt(i,j), top);
            for (int[] d : new int[][]{{-1,0},{1,0},{0,-1},{0,1}}) {
                int ni = i+d[0], nj = j+d[1];
                if (ni>=0 && ni<m && nj>=0 && nj<n && g[ni][nj]==1) unite.accept(idx.applyAsInt(i,j), idx.applyAsInt(ni,nj));
            }
        }
        int[] ans = new int[hits.length];
        for (int k = hits.length-1; k >= 0; k--) {
            int i = hits[k][0], j = hits[k][1];
            if (grid[i][j] == 0) continue;
            g[i][j] = 1;
            int pre = sz[find.applyAsInt(top)];
            for (int[] d : new int[][]{{-1,0},{1,0},{0,-1},{0,1}}) {
                int ni = i+d[0], nj = j+d[1];
                if (ni>=0 && ni<m && nj>=0 && nj<n && g[ni][nj]==1) unite.accept(idx.applyAsInt(i,j), idx.applyAsInt(ni,nj));
            }
            if (i == 0) unite.accept(idx.applyAsInt(i,j), top);
            int post = sz[find.applyAsInt(top)];
            ans[k] = Math.max(0, post-pre-1);
        }
        return ans;
    }
}
 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

class Solution {
    fun hitBricks(grid: Array<IntArray>, hits: Array<IntArray>): IntArray {
        val m = grid.size
        val n = grid[0].size
        val g = Array(m) { grid[it].clone() }
        for (h in hits) g[h[0]][h[1]] = if (g[h[0]][h[1]] == 1) 2 else 0
        val p = IntArray(m*n+1) { it }
        val sz = IntArray(m*n+1) { 1 }
        val top = m*n
        fun find(x: Int): Int { var x0 = x; while (x0 != p[x0]) { p[x0] = p[p[x0]]; x0 = p[x0] }; return x0 }
        fun unite(x: Int, y: Int) { val fx = find(x); val fy = find(y); if (fx != fy) { p[fx] = fy; sz[fy] += sz[fx] } }
        fun idx(i: Int, j: Int) = i*n+j
        for (i in 0 until m) for (j in 0 until n) if (g[i][j] == 1) {
            if (i == 0) unite(idx(i,j), top)
            for ((di, dj) in listOf(-1 to 0, 1 to 0, 0 to -1, 0 to 1)) {
                val ni = i+di; val nj = j+dj
                if (ni in 0 until m && nj in 0 until n && g[ni][nj]==1) unite(idx(i,j), idx(ni,nj))
            }
        }
        val ans = IntArray(hits.size)
        for (k in hits.size-1 downTo 0) {
            val (i, j) = hits[k]
            if (grid[i][j] == 0) continue
            g[i][j] = 1
            val pre = sz[find(top)]
            for ((di, dj) in listOf(-1 to 0, 1 to 0, 0 to -1, 0 to 1)) {
                val ni = i+di; val nj = j+dj
                if (ni in 0 until m && nj in 0 until n && g[ni][nj]==1) unite(idx(i,j), idx(ni,nj))
            }
            if (i == 0) unite(idx(i,j), top)
            val post = sz[find(top)]
            ans[k] = maxOf(0, post-pre-1)
        }
        return ans
    }
}
 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
48

class Solution:
    def hitBricks(self, grid: list[list[int]], hits: list[list[int]]) -> list[int]:
        m, n = len(grid), len(grid[0])
        g = [row[:] for row in grid]
        for i, j in hits:
            if g[i][j] == 1:
                g[i][j] = 2
            else:
                g[i][j] = 0
        p = list(range(m*n+1))
        sz = [1]*(m*n+1)
        def find(x):
            while x != p[x]:
                p[x] = p[p[x]]
                x = p[x]
            return x
        def unite(x, y):
            x, y = find(x), find(y)
            if x != y:
                p[x] = y
                sz[y] += sz[x]
        top = m*n
        def idx(i, j): return i*n+j
        for i in range(m):
            for j in range(n):
                if g[i][j] == 1:
                    if i == 0:
                        unite(idx(i,j), top)
                    for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
                        ni, nj = i+di, j+dj
                        if 0<=ni<m and 0<=nj<n and g[ni][nj]==1:
                            unite(idx(i,j), idx(ni,nj))
        ans = [0]*len(hits)
        for k in range(len(hits)-1, -1, -1):
            i, j = hits[k]
            if grid[i][j] == 0:
                continue
            g[i][j] = 1
            pre = sz[find(top)]
            for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
                ni, nj = i+di, j+dj
                if 0<=ni<m and 0<=nj<n and g[ni][nj]==1:
                    unite(idx(i,j), idx(ni,nj))
            if i == 0:
                unite(idx(i,j), top)
            post = sz[find(top)]
            ans[k] = max(0, post-pre-1)
        return ans
 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

impl Solution {
    pub fn hit_bricks(grid: Vec<Vec<i32>>, hits: Vec<Vec<i32>>) -> Vec<i32> {
        let m = grid.len();
        let n = grid[0].len();
        let mut g = grid.clone();
        for h in &hits {
            if g[h[0]][h[1]] == 1 {
                g[h[0]][h[1]] = 2;
            } else {
                g[h[0]][h[1]] = 0;
            }
        }
        let mut p: Vec<usize> = (0..=m*n).collect();
        let mut sz = vec![1; m*n+1];
        fn find(p: &mut Vec<usize>, x: usize) -> usize {
            if p[x] != x { p[x] = find(p, p[x]); }
            p[x]
        }
        fn unite(p: &mut Vec<usize>, sz: &mut Vec<i32>, x: usize, y: usize) {
            let x = find(p, x);
            let y = find(p, y);
            if x != y {
                p[x] = y;
                sz[y] += sz[x];
            }
        }
        let top = m*n;
        let idx = |i: usize, j: usize| i*n+j;
        for i in 0..m {
            for j in 0..n {
                if g[i][j] == 1 {
                    if i == 0 {
                        unite(&mut p, &mut sz, idx(i,j), top);
                    }
                    for (di, dj) in [(-1,0),(1,0),(0,-1),(0,1)] {
                        let ni = i as isize + di;
                        let nj = j as isize + dj;
                        if ni>=0 && ni<m as isize && nj>=0 && nj<n as isize && g[ni as usize][nj as usize]==1 {
                            unite(&mut p, &mut sz, idx(i,j), idx(ni as usize, nj as usize));
                        }
                    }
                }
            }
        }
        let mut ans = vec![0; hits.len()];
        for k in (0..hits.len()).rev() {
            let i = hits[k][0];
            let j = hits[k][1];
            if grid[i][j] == 0 { continue; }
            g[i][j] = 1;
            let pre = sz[find(&mut p, top)];
            for (di, dj) in [(-1,0),(1,0),(0,-1),(0,1)] {
                let ni = i as isize + di;
                let nj = j as isize + dj;
                if ni>=0 && ni<m as isize && nj>=0 && nj<n as isize && g[ni as usize][nj as usize]==1 {
                    unite(&mut p, &mut sz, idx(i,j), idx(ni as usize, nj as usize));
                }
            }
            if i == 0 {
                unite(&mut p, &mut sz, idx(i,j), top);
            }
            let post = sz[find(&mut p, top)];
            ans[k] = (post-pre-1).max(0);
        }
        ans
    }
}

Complexity

  • ⏰ Time complexity: O(m*n + q*α(m*n)) where q = len(hits), α is the inverse Ackermann function.
  • 🧺 Space complexity: O(m*n) — For the union-find structure and grid copy.