Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

803. Bricks Falling When Hit - Leetcode Solution

Code Implementation

class Solution:
    def hitBricks(self, grid, hits):
        m, n = len(grid), len(grid[0])
        copy = [row[:] for row in grid]
        for i, j in hits:
            copy[i][j] = 0

        parent = [i for i in range(m * n + 1)]
        size = [1] * (m * n + 1)

        def index(x, y):
            return x * n + y

        def find(x):
            while x != parent[x]:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(x, y):
            xr, yr = find(x), find(y)
            if xr == yr:
                return
            if size[xr] < size[yr]:
                parent[xr] = yr
                size[yr] += size[xr]
            else:
                parent[yr] = xr
                size[xr] += size[yr]

        def top():
            return size[find(m * n)] - 1

        for j in range(n):
            if copy[0][j]:
                union(j, m * n)

        for i in range(m):
            for j in range(n):
                if copy[i][j]:
                    for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                        ni, nj = i+dx, j+dy
                        if 0 <= ni < m and 0 <= nj < n and copy[ni][nj]:
                            union(index(i,j), index(ni,nj))

        res = []
        for i, j in reversed(hits):
            if grid[i][j] == 0:
                res.append(0)
                continue
            preTop = top()
            copy[i][j] = 1
            for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                ni, nj = i+dx, j+dy
                if 0 <= ni < m and 0 <= nj < n and copy[ni][nj]:
                    union(index(i,j), index(ni,nj))
            if i == 0:
                union(index(i,j), m*n)
            curTop = top()
            res.append(max(0, curTop - preTop))
        return res[::-1]
      
class Solution {
public:
    vector hitBricks(vector>& grid, vector>& hits) {
        int m = grid.size(), n = grid[0].size();
        vector> copy = grid;
        for (auto& hit : hits) copy[hit[0]][hit[1]] = 0;
        vector parent(m*n+1), size(m*n+1, 1);
        for (int i = 0; i < m*n+1; ++i) parent[i] = i;
        auto index = [&](int x, int y) { return x*n + y; };
        function find = [&](int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        };
        auto unite = [&](int x, int y) {
            int xr = find(x), yr = find(y);
            if (xr == yr) return;
            if (size[xr] < size[yr]) {
                parent[xr] = yr;
                size[yr] += size[xr];
            } else {
                parent[yr] = xr;
                size[xr] += size[yr];
            }
        };
        auto top = [&]() { return size[find(m*n)] - 1; };

        for (int j = 0; j < n; ++j)
            if (copy[0][j]) unite(j, m*n);

        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (copy[i][j]) {
                    for (auto d : vector>{{-1,0},{1,0},{0,-1},{0,1}}) {
                        int ni = i+d.first, nj = j+d.second;
                        if (ni>=0 && ni<m && nj>=0 && nj<n && copy[ni][nj])
                            unite(index(i,j), index(ni,nj));
                    }
                }
        vector res;
        for (int k = hits.size()-1; k >= 0; --k) {
            int i = hits[k][0], j = hits[k][1];
            if (grid[i][j] == 0) { res.push_back(0); continue; }
            int preTop = top();
            copy[i][j] = 1;
            for (auto d : vector>{{-1,0},{1,0},{0,-1},{0,1}}) {
                int ni = i+d.first, nj = j+d.second;
                if (ni>=0 && ni<m && nj>=0 && nj<n && copy[ni][nj])
                    unite(index(i,j), index(ni,nj));
            }
            if (i == 0) unite(index(i,j), m*n);
            int curTop = top();
            res.push_back(max(0, curTop-preTop));
        }
        reverse(res.begin(), res.end());
        return res;
    }
};
      
class Solution {
    int m, n;
    int[] parent, size;
    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    public int[] hitBricks(int[][] grid, int[][] hits) {
        m = grid.length; n = grid[0].length;
        int[][] copy = new int[m][n];
        for (int i = 0; i < m; ++i)
            copy[i] = grid[i].clone();
        for (int[] hit : hits)
            copy[hit[0]][hit[1]] = 0;
        parent = new int[m*n+1];
        size = new int[m*n+1];
        for (int i = 0; i < m*n+1; ++i) {
            parent[i] = i; size[i] = 1;
        }
        for (int j = 0; j < n; ++j)
            if (copy[0][j]==1) union(j, m*n);

        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (copy[i][j]==1)
                    for (int[] d : dirs) {
                        int ni = i+d[0], nj = j+d[1];
                        if (ni>=0 && ni<m && nj>=0 && nj<n && copy[ni][nj]==1)
                            union(index(i,j), index(ni,nj));
                    }
        int[] res = 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) { res[k]=0; continue; }
            int preTop = top();
            copy[i][j] = 1;
            for (int[] d : dirs) {
                int ni = i+d[0], nj = j+d[1];
                if (ni>=0 && ni<m && nj>=0 && nj<n && copy[ni][nj]==1)
                    union(index(i,j), index(ni,nj));
            }
            if (i == 0) union(index(i,j), m*n);
            int curTop = top();
            res[k] = Math.max(0, curTop-preTop);
        }
        return res;
    }
    int index(int x, int y) { return x*n+y; }
    int find(int x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    void union(int x, int y) {
        int xr = find(x), yr = find(y);
        if (xr == yr) return;
        if (size[xr] < size[yr]) {
            parent[xr] = yr;
            size[yr] += size[xr];
        } else {
            parent[yr] = xr;
            size[xr] += size[yr];
        }
    }
    int top() { return size[find(m*n)]-1; }
}
      
var hitBricks = function(grid, hits) {
    let m = grid.length, n = grid[0].length;
    let copy = grid.map(row => row.slice());
    for (let [i, j] of hits) copy[i][j] = 0;
    let parent = Array(m*n+1).fill(0).map((_,i)=>i);
    let size = Array(m*n+1).fill(1);
    let index = (x, y) => x*n + y;
    function find(x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    function union(x, y) {
        let xr = find(x), yr = find(y);
        if (xr == yr) return;
        if (size[xr] < size[yr]) {
            parent[xr] = yr;
            size[yr] += size[xr];
        } else {
            parent[yr] = xr;
            size[xr] += size[yr];
        }
    }
    function top() { return size[find(m*n)]-1; }

    for (let j = 0; j < n; ++j)
        if (copy[0][j]) union(j, m*n);

    for (let i = 0; i < m; ++i)
        for (let j = 0; j < n; ++j)
            if (copy[i][j])
                for (let [dx,dy] of [[-1,0],[1,0],[0,-1],[0,1]]) {
                    let ni = i+dx, nj = j+dy;
                    if (ni>=0 && ni<m && nj>=0 && nj<n && copy[ni][nj])
                        union(index(i,j), index(ni,nj));
                }
    let res = [];
    for (let k = hits.length-1; k >= 0; --k) {
        let [i, j] = hits[k];
        if (grid[i][j] == 0) { res.push(0); continue; }
        let preTop = top();
        copy[i][j] = 1;
        for (let [dx,dy] of [[-1,0],[1,0],[0,-1],[0,1]]) {
            let ni = i+dx, nj = j+dy;
            if (ni>=0 && ni<m && nj>=0 && nj<n && copy[ni][nj])
                union(index(i,j), index(ni,nj));
        }
        if (i == 0) union(index(i,j), m*n);
        let curTop = top();
        res.push(Math.max(0, curTop-preTop));
    }
    return res.reverse();
};

Problem Description

You are given a 2D grid representing a wall of bricks, where each cell contains either a 1 (brick) or 0 (empty). The top row is connected to the ceiling, and any brick is stable if it is either in the top row or directly or indirectly connected to the top row via other bricks.

You are also given a list of hits, where each hit is a pair (i, j) indicating a brick to be removed (if present). After each hit, some bricks may fall if they are no longer stable (no longer connected to the top row).

For each hit, return the number of bricks that fall as a result (excluding the brick hit itself).

Constraints:

  • Each hit removes at most one brick.
  • Bricks that fall must be counted after each hit.
  • Bricks are stable only if connected to the top row.
  • Do not modify the original grid except as part of the process.

Thought Process

The first idea might be to simulate each hit: remove the brick, then check for all bricks that are no longer connected to the top. This could be done with a depth-first or breadth-first search after every hit. However, this is inefficient, since each search could visit the whole grid, and there could be many hits.

To optimize, notice that the problem is actually about connectivity: after each hit, we need to know which bricks are still connected to the ceiling. If we can efficiently track which bricks are connected to the top, we can quickly answer the question after each hit.

This leads us to use a Union-Find (Disjoint Set Union) structure. By treating the top row as a special "ceiling" node, and connecting bricks together if they're adjacent, we can efficiently determine which bricks are stable. Instead of simulating each hit forward, we can process all hits in reverse: first remove all bricks to be hit, build the initial stable structure, then add bricks back one by one, updating connectivity and counting how many bricks become stable (i.e., would not have fallen).

Solution Approach

  • 1. Mark All Hits: Make a copy of the grid and "remove" all bricks that will be hit by setting those cells to 0.
  • 2. Union-Find Setup: Use Union-Find to track connected components. Each brick is a node, and we add an extra "ceiling" node. Any brick in the top row connects to the ceiling.
  • 3. Initial Union: Go through the grid after all hits, and union adjacent bricks. Also, connect any top-row brick to the ceiling node.
  • 4. Reverse Process: Now process the hits in reverse order. For each hit:
    • If the original cell was empty, nothing happens (append 0).
    • If it was a brick, add it back, union with adjacent bricks, and if it's in the top row, union with the ceiling.
    • Calculate how many more bricks are now connected to the ceiling (i.e., became stable), compared to before. The difference (minus one for the brick just added back) is the number of bricks that would have fallen after the hit.
  • 5. Return the Result: Reverse the result list to match the original order of hits.

The Union-Find structure is used because it allows us to efficiently merge sets (bricks connected together) and quickly find the size of the set connected to the ceiling.

Example Walkthrough

Input:
grid = [[1,0,0,0],[1,1,1,0]]
hits = [[1,0]]

  1. Remove hits: Remove brick at (1,0), so grid becomes:
    [[1,0,0,0],[0,1,1,0]]
  2. Union-Find setup: Connect bricks in top row to ceiling. Connect adjacent bricks (e.g., (1,1) to (1,2)).
  3. Process hits in reverse:
    • Add back brick (1,0). It is adjacent to (0,0) (in top row, so stable) and (1,1). After union, both (1,0) and (1,1) become connected to the ceiling.
    • Before adding, only (0,0) was stable. After adding, (1,0) and (1,1) are now connected to ceiling. Only (1,1) is new (excluding the brick just added back).
    • So, 2 bricks are now stable, but one is the brick itself, so 1 brick "fell" as a result of the hit.
  4. Return: [2]

Time and Space Complexity

  • Brute-force Approach: For each hit, perform a DFS or BFS to check which bricks are still connected to the ceiling. This takes O(H * M * N) time, where H is the number of hits, and M, N are grid dimensions. This is very slow for large grids.
  • Optimized Approach (Union-Find): Each union and find operation is nearly constant time (amortized O(α(N)), where α is the inverse Ackermann function). The total number of operations is proportional to the number of cells and hits, so the total time is O(M * N + H * α(M * N)), which is very efficient.
  • Space Complexity: We use O(M * N) space for the Union-Find structure and grid copies.

Summary

The key insight is to process the hits in reverse, using a Union-Find structure to efficiently track which bricks are connected to the ceiling. This avoids repeated searches and leverages the efficiency of Union-Find for dynamic connectivity problems. By marking all hits first, building the initial stable structure, and then adding bricks back one at a time, we can calculate the number of falling bricks for each hit in optimal time.