Bricks Falling When Hit
Problem
Given an m x n grid where 1 is a brick, bricks are stable if connected (4-directionally) to the top row or another stable brick. After a sequence of hits that erase a brick if present, return for each hit how many other bricks fall.
grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]][2]class DSU:
def __init__(self, n):
self.p = list(range(n)); self.sz = [1] * n
def find(self, x):
while self.p[x] != x:
self.p[x] = self.p[self.p[x]]; x = self.p[x]
return x
def union(self, a, b):
a, b = self.find(a), self.find(b)
if a == b: return
if self.sz[a] < self.sz[b]: a, b = b, a
self.p[b] = a; self.sz[a] += self.sz[b]
def hitBricks(grid, hits):
m, n = len(grid), len(grid[0])
g = [row[:] for row in grid]
for r, c in hits: g[r][c] = 0
dsu = DSU(m * n + 1); ROOF = m * n
idx = lambda r, c: r * n + c
def connect(r, c):
if r == 0: dsu.union(ROOF, idx(r, c))
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r+dr, c+dc
if 0<=nr<m and 0<=nc<n and g[nr][nc]==1: dsu.union(idx(r,c), idx(nr,nc))
for r in range(m):
for c in range(n):
if g[r][c] == 1: connect(r, c)
res = []
for r, c in reversed(hits):
if grid[r][c] == 0: res.append(0); continue
prev = dsu.sz[dsu.find(ROOF)]
g[r][c] = 1; connect(r, c)
now = dsu.sz[dsu.find(ROOF)]
res.append(max(0, now - prev - 1))
return res[::-1]var hitBricks = function(grid, hits) {
const m = grid.length, n = grid[0].length;
const g = grid.map(r => r.slice());
for (const [r, c] of hits) g[r][c] = 0;
const ROOF = m * n;
const p = Array.from({length: m*n+1}, (_, i) => i), sz = new Array(m*n+1).fill(1);
const find = (x) => { while (p[x] !== x) { p[x] = p[p[x]]; x = p[x]; } return x; };
const union = (a, b) => { a = find(a); b = find(b); if (a===b) return; if (sz[a]<sz[b]) [a,b]=[b,a]; p[b]=a; sz[a]+=sz[b]; };
const idx = (r, c) => r*n + c;
const connect = (r, c) => {
if (r === 0) union(ROOF, idx(r, c));
for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {
const nr=r+dr, nc=c+dc;
if (nr>=0&&nr<m&&nc>=0&&nc<n&&g[nr][nc]===1) union(idx(r,c), idx(nr,nc));
}
};
for (let r=0;r<m;r++) for (let c=0;c<n;c++) if (g[r][c]===1) connect(r, c);
const res = [];
for (let i = hits.length - 1; i >= 0; i--) {
const [r, c] = hits[i];
if (grid[r][c] === 0) { res.push(0); continue; }
const prev = sz[find(ROOF)];
g[r][c] = 1; connect(r, c);
const now = sz[find(ROOF)];
res.push(Math.max(0, now - prev - 1));
}
return res.reverse();
};class Solution {
int[] p, sz;
int find(int x) { while (p[x]!=x) { p[x]=p[p[x]]; x=p[x]; } return x; }
void union_(int a, int b) { a=find(a); b=find(b); if (a==b) return; if (sz[a]<sz[b]) { int t=a; a=b; b=t; } p[b]=a; sz[a]+=sz[b]; }
public int[] hitBricks(int[][] grid, int[][] hits) {
int m = grid.length, n = grid[0].length, ROOF = m * n;
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]] = 0;
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[][] D = {{-1,0},{1,0},{0,-1},{0,1}};
java.util.function.BiConsumer<Integer,Integer> connect = (r, c) -> {
if (r == 0) union_(ROOF, r*n+c);
for (int[] d : D) { int nr=r+d[0], nc=c+d[1]; if (nr>=0&&nr<m&&nc>=0&&nc<n&&g[nr][nc]==1) union_(r*n+c, nr*n+nc); }
};
for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) if (g[r][c]==1) connect.accept(r, c);
int[] res = new int[hits.length];
for (int i = hits.length-1; i >= 0; i--) {
int r = hits[i][0], c = hits[i][1];
if (grid[r][c] == 0) continue;
int prev = sz[find(ROOF)]; g[r][c] = 1; connect.accept(r, c);
res[i] = Math.max(0, sz[find(ROOF)] - prev - 1);
}
return res;
}
}class Solution {
vector<int> p, sz;
int find(int x) { while (p[x]!=x) { p[x]=p[p[x]]; x=p[x]; } return x; }
void unite(int a, int b) { a=find(a); b=find(b); if (a==b) return; if (sz[a]<sz[b]) swap(a,b); p[b]=a; sz[a]+=sz[b]; }
public:
vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
int m = grid.size(), n = grid[0].size(), ROOF = m*n;
auto g = grid;
for (auto& h : hits) g[h[0]][h[1]] = 0;
p.assign(m*n+1, 0); sz.assign(m*n+1, 1);
for (int i = 0; i <= m*n; i++) p[i] = i;
vector<pair<int,int>> D = {{-1,0},{1,0},{0,-1},{0,1}};
auto connect = [&](int r, int c) {
if (r == 0) unite(ROOF, r*n+c);
for (auto& d : D) { int nr=r+d.first, nc=c+d.second; if (nr>=0&&nr<m&&nc>=0&&nc<n&&g[nr][nc]==1) unite(r*n+c, nr*n+nc); }
};
for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) if (g[r][c]==1) connect(r, c);
vector<int> res(hits.size(), 0);
for (int i = hits.size()-1; i >= 0; i--) {
int r = hits[i][0], c = hits[i][1];
if (grid[r][c] == 0) continue;
int prev = sz[find(ROOF)]; g[r][c] = 1; connect(r, c);
res[i] = max(0, sz[find(ROOF)] - prev - 1);
}
return res;
}
};Explanation
Removing a brick and then figuring out what falls is messy, because erasing one brick can disconnect a whole chunk. The clever fix is to process the hits in reverse — instead of erasing bricks, we add them back one by one, which is much easier with union-find.
First we apply all hits up front, then connect every remaining brick to its neighbours, plus connect top-row bricks to a special ROOF node. The size of the group containing ROOF tells us how many bricks are currently stable (attached to the top).
Now we replay hits backward. For each one, we note the roof group's size, put the brick back, reconnect it, and check the new roof size. The number of bricks that newly became stable is the count that would have fallen in the forward direction — we subtract 1 for the re-added brick itself, and clamp at 0.
Example: grid=[[1,0,0,0],[1,1,1,0]], hits=[[1,0]]. With (1,0) erased, the bricks at (1,1) and (1,2) hang off it and are unsupported. Adding (1,0) back reconnects them to the roof, so now - prev - 1 = 2 bricks fell, giving [2].