Bricks Falling When Hit

Hard
1735.

Bricks Falling When Hit

Bricks Falling When Hit is a hard coding problem on arrays, matrix and union find, asked in Amazon and Google interviews.

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.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
  • every brick of grid is stable before the first erasure
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @param {number[][]} hits
 * @return {number[]}
 */
var hitBricks = function(grid, hits) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.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
  • every brick of grid is stable before the first erasure

Hints for Bricks Falling When Hit

  1. 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?

  2. Hint 2

    Erase every hit cell first, union the remaining bricks, and connect the top row to a virtual "roof" node.

  3. 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

  1. Copy the grid and erase every hit cell. Make one union-find node per cell plus a roof node.
  2. Union every remaining brick with its brick neighbours, and every top-row brick with the roof.
  3. 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 ans

Java

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