Bricks Falling When Hit — Solution in Python, Java & C++
Bricks Falling When Hit solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Bricks Falling When Hit is a hard coding problem on arrays, matrix and union find, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Matrix, Union Find
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an m x n binary grid where 1 is a brick and 0 is empty space. A brick is stable if it is in the top row, or if it shares an edge with at least one stable brick.
You are also given hits, a sequence of cells to erase. For hits[i] = [xi, yi], the brick at that cell (if there is one) disappears. Afterwards, every brick that is no longer stable falls at once and is removed from the grid; falling bricks never land on other bricks.
Return an array result where result[i] is the number of bricks that fall after the i-th erasure. The erased brick itself does not count.
Example 1
Input: grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
Output: [2]
Explanation: Erasing (1,0) leaves (1,1) and (1,2) with no path to the top row, so both fall.
Example 2
Input: grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
Output: [0,0]
Explanation: Each erasure removes a brick but leaves every remaining brick stable.
Example 3
Input: grid = [[1],[1],[1]], hits = [[1,0],[0,0]]
Output: [1,0]
Explanation: Erasing the middle brick drops the bottom one; the top brick is then erased with nothing below it.
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 200grid[i][j] is 0 or 11 <= hits.length <= 4 * 10^4hits[i].length == 20 <= xi <= m - 10 <= yi <= n - 1all (xi, yi) are uniqueevery brick of grid is stable before the first erasure
Hints for Bricks Falling When Hit
Hint 1
Erasing breaks connectivity, which is hard to maintain. Adding bricks only joins components — and that is what a union-find is good at. Can you play the hits backwards?
Hint 2
Erase every hit cell first, union the remaining bricks, and connect the top row to a virtual "roof" node.
Hint 3
Now restore the hits in reverse. When a brick is put back, the roof's component grows; the growth minus the restored brick itself is how many bricks that hit made fall. A hit on an empty cell made nothing fall.
How to solve Bricks Falling When Hit
Run time backwards. In reverse, each hit adds a brick back, and the bricks that fell are exactly those that become attached to the roof by that addition. Union-find with component sizes measures this in near-constant time per hit.
Approach
- Copy the grid and erase every hit cell. Make one union-find node per cell plus a roof node.
- Union every remaining brick with its brick neighbours, and every top-row brick with the roof.
- For the hits from last to first: if the original cell was empty, the answer is 0. Otherwise record the roof component's size, restore the brick, union it with the roof (if in the top row) and with neighbouring bricks, and set the answer to
max(0, newSize - oldSize - 1).
Why it works
Running forward, the bricks that fall at hit i are those connected to the roof only through the brick removed at hit i. Running backward, adding that brick back attaches exactly those bricks (plus the brick itself) to the roof's component. When the restored brick does not touch the roof's component, the size does not change and the max(0, …) keeps the answer at 0.
Complexity
- Time —
O((m · n + h) · α(m · n)) - Space —
O(m · n)
Pitfalls
- A hit on an empty cell makes nothing fall — and it must not restore a brick that was never there.
- Subtract 1 for the restored brick itself; it was erased, it did not fall.
- Bricks that fell earlier are gone for good: in reverse they simply have not been attached yet.
Reference solution
Python
from typing import List
def hitBricks(grid: List[List[int]], hits: List[List[int]]) -> List[int]:
m, n = len(grid), len(grid[0])
roof = m * n
parent = list(range(m * n + 1))
size = [1] * (m * n + 1)
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra == rb:
return
if size[ra] < size[rb]:
ra, rb = rb, ra
parent[rb] = ra
size[ra] += size[rb]
g = [row[:] for row in grid]
for r, c in hits:
g[r][c] = 0
for r in range(m):
for c in range(n):
if g[r][c] == 1:
if r == 0:
union(c, roof)
if r > 0 and g[r - 1][c] == 1:
union(r * n + c, (r - 1) * n + c)
if c > 0 and g[r][c - 1] == 1:
union(r * n + c, r * n + c - 1)
ans = [0] * len(hits)
for i in range(len(hits) - 1, -1, -1):
r, c = hits[i]
if grid[r][c] == 0:
continue
before = size[find(roof)]
g[r][c] = 1
if r == 0:
union(c, roof)
for a, b in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= a < m and 0 <= b < n and g[a][b] == 1:
union(r * n + c, a * n + b)
ans[i] = max(0, size[find(roof)] - before - 1)
return ansJava
static int[] par, sz;
static int find(int x) {
while (par[x] != x) { par[x] = par[par[x]]; x = par[x]; }
return x;
}
static void union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return;
if (sz[ra] < sz[rb]) { int t = ra; ra = rb; rb = t; }
par[rb] = ra;
sz[ra] += sz[rb];
}
public static int[] hitBricks(int[][] grid, int[][] hits) {
int m = grid.length, n = grid[0].length, roof = m * n;
par = new int[m * n + 1];
sz = new int[m * n + 1];
for (int i = 0; i <= m * n; i++) { par[i] = i; sz[i] = 1; }
int[][] g = new int[m][];
for (int r = 0; r < m; r++) g[r] = grid[r].clone();
for (int[] h : hits) g[h[0]][h[1]] = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (g[r][c] != 1) continue;
if (r == 0) union(c, roof);
if (r > 0 && g[r - 1][c] == 1) union(r * n + c, (r - 1) * n + c);
if (c > 0 && g[r][c - 1] == 1) union(r * n + c, r * n + c - 1);
}
}
int[] DR = {1, -1, 0, 0}, DC = {0, 0, 1, -1};
int[] ans = new int[hits.length];
for (int k = hits.length - 1; k >= 0; k--) {
int x = hits[k][0], y = hits[k][1];
if (grid[x][y] == 0) continue;
int before = sz[find(roof)];
g[x][y] = 1;
if (x == 0) union(y, roof);
for (int d = 0; d < 4; d++) {
int a = x + DR[d], b = y + DC[d];
if (a >= 0 && a < m && b >= 0 && b < n && g[a][b] == 1) union(x * n + y, a * n + b);
}
ans[k] = Math.max(0, sz[find(roof)] - before - 1);
}
return ans;
}C++
vector<int> par, sz;
int findRoot(int x) {
while (par[x] != x) { par[x] = par[par[x]]; x = par[x]; }
return x;
}
void unite(int a, int b) {
int ra = findRoot(a), rb = findRoot(b);
if (ra == rb) return;
if (sz[ra] < sz[rb]) swap(ra, rb);
par[rb] = ra;
sz[ra] += sz[rb];
}
vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
int m = grid.size(), n = grid[0].size(), roof = m * n;
par.assign(m * n + 1, 0);
sz.assign(m * n + 1, 1);
for (int i = 0; i <= m * n; i++) par[i] = i;
vector<vector<int>> g = grid;
for (auto& h : hits) g[h[0]][h[1]] = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (g[r][c] != 1) continue;
if (r == 0) unite(c, roof);
if (r > 0 && g[r - 1][c] == 1) unite(r * n + c, (r - 1) * n + c);
if (c > 0 && g[r][c - 1] == 1) unite(r * n + c, r * n + c - 1);
}
}
int DR[4] = {1, -1, 0, 0}, DC[4] = {0, 0, 1, -1};
vector<int> ans(hits.size(), 0);
for (int k = (int) hits.size() - 1; k >= 0; k--) {
int x = hits[k][0], y = hits[k][1];
if (grid[x][y] == 0) continue;
int before = sz[findRoot(roof)];
g[x][y] = 1;
if (x == 0) unite(y, roof);
for (int d = 0; d < 4; d++) {
int a = x + DR[d], b = y + DC[d];
if (a >= 0 && a < m && b >= 0 && b < n && g[a][b] == 1) unite(x * n + y, a * n + b);
}
ans[k] = max(0, sz[findRoot(roof)] - before - 1);
}
return ans;
}JavaScript
var hitBricks = function(grid, hits) {
var m = grid.length, n = grid[0].length, roof = m * n;
var parent = [], size = [];
for (var i = 0; i <= m * n; i++) { parent.push(i); size.push(1); }
var find = function(x) {
while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
};
var union = function(a, b) {
var ra = find(a), rb = find(b);
if (ra === rb) return;
if (size[ra] < size[rb]) { var t = ra; ra = rb; rb = t; }
parent[rb] = ra;
size[ra] += size[rb];
};
var g = [];
for (var r0 = 0; r0 < m; r0++) g.push(grid[r0].slice());
for (var h = 0; h < hits.length; h++) g[hits[h][0]][hits[h][1]] = 0;
for (var r = 0; r < m; r++) {
for (var c = 0; c < n; c++) {
if (g[r][c] !== 1) continue;
if (r === 0) union(c, roof);
if (r > 0 && g[r - 1][c] === 1) union(r * n + c, (r - 1) * n + c);
if (c > 0 && g[r][c - 1] === 1) union(r * n + c, r * n + c - 1);
}
}
var DR = [1, -1, 0, 0], DC = [0, 0, 1, -1];
var ans = [];
for (var z = 0; z < hits.length; z++) ans.push(0);
for (var k = hits.length - 1; k >= 0; k--) {
var x = hits[k][0], y = hits[k][1];
if (grid[x][y] === 0) continue;
var before = size[find(roof)];
g[x][y] = 1;
if (x === 0) union(y, roof);
for (var d = 0; d < 4; d++) {
var a = x + DR[d], b = y + DC[d];
if (a >= 0 && a < m && b >= 0 && b < n && g[a][b] === 1) union(x * n + y, a * n + b);
}
ans[k] = Math.max(0, size[find(roof)] - before - 1);
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal