Problem Explanation

In this problem, we have a 2D-grid which represents a top-down view of a wall, where '1's in a cell represent bricks and '0's represent empty spaces.

• A brick is considered "stable" if it is connected to the top of the grid or at least one of its (top, bottom, left or right) neighboring bricks is stable.
• The task is to erase bricks one-by-one from the grid as per the sequence of coordinates provided in "hits" list.
• After each erase operation, some bricks may fall because they're not connected to the top anymore or all of their neighbors have been erased.
• We are asked to return a list of the number of bricks that fall after each erase operation.

Problem Solution

We will use Union Find based solution to solve this problem.

• Firstly, we will mark the bricks to hit as '2' in the grid, then we do union operations for all the remaining '1's.
• Then we erase the bricks from bottom to top. For each erased brick, we add it back to the grid (turn '2' to '1') and unite it with its adjacent bricks.
• If a brick is connected to the top after the union operation, the size of the connected component increases. The increased part is the number of dropped bricks.
• We keep the results in the output list and finally return it.

Walkthrough with an example

Consider an Example: Grid = [[1, 0, 0, 0], [1, 1, 1, 0]], hits = [[1, 0]]

• Initially, the grid has 1s which show the location of bricks and 0s are empty spaces.
• Looking at the 'hits' list, the brick located at (1, 0) is to be removed. It has 2 adjacent bricks at (1, 1) and (1, 2).
• Removing the brick (1, 0) breaks the connection of these 2 adjacent bricks with the top, and they will fall down.
• So, after this remove operation, the total of 2 bricks fall down.

The output will be [2].

Python Solution

1
2python
3dx = [-1, 0, 1, 0]
4dy = [0, 1, 0, -1]
5
6class UnionFind():
7  def __init__(self, n):
8    self.father = [0]*n
9    for i in range(n):
10      self.father[i] = i
11      
12  def find(self, x):
13    if self.father[x] == x:
14      return x
15    self.father[x] = self.find(self.father[x])
16    return self.father[x]
17    
18  def connect(self, a, b):
19    root_a = self.find(a)
20    root_b = self.find(b)
21    if root_a != root_b:
22      self.father[root_a] = root_b
23
24
25def hitBricks(self, grid, hits: List[List[int]]) -> List[int]:
26  m, n = len(grid), len(grid[0])
27  f = UnionFind(m*n + 1)
28  state = [0]*(m*n + 1)
29  
30  virtual_node = m * n
31  
32  def index(x, y):
33    return x * n + y
34
35  def is_valid(x, y):
36    return 0 <= x < m and 0 <= y < n
37  
38  def connect_neighbors(x, y):
39    for i in range(4):
40      newx = x + dx[i]
41      newy = y + dy[i]
42      if is_valid(newx, newy) and state[index(newx, newy)] == 1:
43        f.connect(index(x, y), index(newx, newy))
44  
45  for i in hits:
46    grid[i[0]][i[1]] -= 1
47
48  for i in range(m):
49    for j in range(n):
50      if grid[i][j] == 1:
51        state[index(i, j)] = 1
52  for i in range(n):
53    if state[i] == 1:
54      f.connect(i, virtual_node)
55  for i in range(1, m):
56    for j in range(n):
57      if state[index(i, j)] == 1:
58        connect_neighbors(i, j)
59
60  res = [0]*len(hits)
61
62  for i in range(len(hits)-1, -1, -1):
63    x, y = hits[i][0], hits[i][1]
64    pre_roof = f.find(virtual_node)
65    if grid[x][y] == 0:
66      grid[x][y] += 1
67      if state[index(x, y)] == 0 and is_valid(x, y):
68        state[index(x, y)] = 1
69        if x == 0:
70          f.connect(index(x, y), virtual_node)
71        connect_neighbors(x, y)
72        after_roof = f.find(virtual_node)
73        res[i] = max(0, after_roof - pre_roof - 1)
74    return res

JavaScript Solution

1
2javascript
3function hitBricks(grid, hits) {
4    let m = grid.length;
5    let n = grid[0].length;
6    let size = new Array(m * n).fill(0);
7    let parent = new Array(m * n).fill(0);
8    for (let i = 0; i < m * n; i++) parent[i] = i;
9    let top = m * n;
10
11    const find = x => {
12        if (parent[x] != x) parent[x] = find(parent[x]);
13        return parent[x];
14    }
15    const union = (x, y) => {
16        let rootX = find(x);
17        let rootY = find(y);
18        if (rootX != rootY) {
19            parent[rootX] = rootY;
20            size[rootY] += size[rootX];
21        }
22    }
23    const index = (x, y) => x * n + y;
24    
25    for (let [x, y] of hits) grid[x][y]--;
26    
27    let dx = [-1, 0, 1, 0];
28    let dy = [0, 1, 0, -1];
29    for (let i = 0; i < n; i++) {
30        if (grid[0][i] == 1) {
31            parent[i] = top;
32            size[top]++;
33        }
34    }
35    for (let i = 1; i < m; i++)
36        for (let j = 0; j < n; j++)
37            if (grid[i][j] == 1)
38                if (grid[i - 1][j] == 1) union(index(i, j), index(i - 1, j));
39                else size[index(i,j)] = 1;
40    
41    let ret = new Array(hits.length).fill(0);
42    for (let k = hits.length - 1; k >= 0; k--) {
43        let [i, j] = hits[k];
44        if (++grid[i][j] == 1) {
45            let cnt = 0;
46            if (i == 0) {
47                cnt = size[top];
48                union(j, top);
49            }
50            for (let d = 0; d < 4; d++) {
51                let x = i + dx[d], y = j + dy[d];
52                if (x >= 0 && x < m && y >= 0 && y < n && find(x * n + y) != top)
53                    cnt += size[find(x * n + y)];
54            }
55            ret[k] = Math.max(0, size[find(top)] - cnt - 1);
56        }
57    }
58    return ret;
59}

Java Solution

1
2java
3import java.util.*;
4
5public class BricksFallen {
6    private int[] dr = {0, 1, 0, -1};
7    private int[] dc = {1, 0, -1, 0};
8    private int R, C;
9
10    class DSU {
11        int[] parent;
12        int[] rank;
13        int[] size;
14        DSU(int N) {
15            parent = new int[N];
16            rank = new int[N];
17            size = new int[N];
18            for (int i = 0; i < N; i++) {
19                parent[i] = i;
20                size[i] = 1;
21            }
22            rank[N-1] = Integer.MAX_VALUE;
23        }
24
25        public int find(int x) {
26            if (parent[x] != x) parent[x] = find(parent[x]);
27            return parent[x];
28        }
29
30        public boolean union(int x, int y) {
31            int xr = find(x), yr = find(y);
32            if (xr == yr) return false;
33
34            if (rank[xr] < rank[yr]) {
35                int tmp = xr; xr = yr; yr = tmp;
36            }
37            if (rank[xr] == rank[yr]) rank[xr]++;
38            parent[yr] = xr;
39            size[xr] += size[yr];
40            return true;
41        }
42
43        public int size(int x) {
44            return size[find(x)];
45        }
46    }
47
48    public int[] hitBricks(int[][] grid, int[][] hits) {
49        this.R = grid.length;
50        this.C = grid[0].length;
51
52        DSU dsu = new DSU(R*C + 1);
53        int[][] A = new int[R][C];
54
55        for (int r = 0; r < R; r++)
56            A[r] = grid[r].clone();
57
58        for (int[] hit: hits)
59            A[hit[0]][hit[1]] = 0;
60
61        for (int r = 0; r < R; r++)
62            for (int c = 0; c < C; c++)
63                if (A[r][c] == 1)
64                    connectAround(A, r, c, dsu);
65
66        int t = R*C;
67        int[] ans = new int[hits.length];
68        for (int i = hits.length - 1; i >= 0; i--) {
69            int r = hits[i][0];
70            int c = hits[i][1];
71
72            A[r][c] = 1;
73            int oldSize = dsu.size(t);
74
75            if (r == 0)
76                dsu.union(c, t);
77            if (r > 0 && A[r-1][c] == 1)
78                dsu.union((r-1)*C + c, r*C + c);
79            if (r + 1 < R && A[r+1][c] == 1)
80                dsu.union((r+1)*C + c, r*C + c);
81            if (c - 1 >= 0 && A[r][c-1] == 1)
82                dsu.union(r*C + (c-1), r*C + c);
83            if (c + 1 < C && A[r][c+1] == 1)
84                dsu.union(r*C + (1+c), r*C + c);
85
86            ans[i] = Math.max(0, dsu.size(t) - oldSize - 1);
87        }
88        return ans;
89    }
90
91    public void connectAround(int[][] A, int r, int c, DSU dsu) {
92        int p1 = r*C + c;
93        if (r == 0)
94            dsu.union(p1, R*C);
95
96        for (int dd = 0; dd < 4; dd++) {
97            int rr = r + dr[dd];
98            int cc = c + dc[dd];
99            if (0 <= rr && rr < R && 0 <= cc && cc < C && A[rr][cc] == 1)
100                dsu.union(p1, rr*C + cc);
101        }
102    }
103}