Course4all
Join us on telegram
Home/dsa/Union Find/Bricks Falling When Hit

Bricks Falling When Hit

Master this topic with zero to advance depth.

Bricks Falling When Hit

You are given an m×nm \times n binary grid where 1 represents a brick. A brick will not fall if it is connected to the top row (row index 0) or another brick that will not fall. When a brick is 'hit', it turns into 0. Return the number of bricks that fall after each hit.

Reverse Union-Find Strategy

  1. Remove all hit bricks first.
  2. Build the initial graph for the remaining bricks.
  3. Add hit bricks back in reverse order.
  4. The number of new bricks connected to the top row (excluding the re-added brick itself) is the number of falling bricks for that hit.
Hard

Examples

Input: grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
Output: [2]
Approach 1

Level II: BFS (Exhaustive Simulation)

Intuition

This approach directly simulates the process for each hit. After removing a brick, we perform a broad connectivity check (using BFS/DFS) to see which bricks are still connected to the top row. Any brick that was previously connected but is no longer is counted as 'fallen'.

⏱ O(K \cdot M \cdot N) where K is number of hits.💾 O(M \cdot N).
java
class Solution {
    public int[] hitBricks(int[][] grid, int[][] hits) {
        int m = grid.length, n = grid[0].length;
        int[] res = new int[hits.length];
        for (int i = 0; i < hits.length; i++) {
            int r = hits[i][0], c = hits[i][1];
            if (grid[r][c] == 0) continue;
            grid[r][c] = 0;
            res[i] = countFalling(grid);
        }
        return res;
    }
    private int countFalling(int[][] g) {
        int m = g.length, n = g[0].length; boolean[][] v = new boolean[m][n];
        for (int j = 0; j < n; j++) if (g[0][j] == 1 && !v[0][j]) dfs(g, 0, j, v);
        int count = 0;
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (g[i][j] == 1 && !v[i][j]) count++;
        return count;
    }
    private void dfs(int[][] g, int r, int c, boolean[][] v) {
        if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] == 0 || v[r][c]) return;
        v[r][c] = true; dfs(g, r + 1, c, v); dfs(g, r - 1, c, v); dfs(g, r, c + 1, v); dfs(g, r, c - 1, v);
    }
}
Approach 2

Level III: Reverse DSU (Connectivity Recovery)

Intuition

Tracking 'falling' bricks is hard. Tracking 'recovered' bricks by adding them back in reverse is much easier. Use a dummy node to represent the 'ceiling' (connected to all row 0 bricks).

⏱ O((H + M*N) * alpha(M*N)) where H is hits.💾 O(M*N).
java
class Solution {
    public int[] hitBricks(int[][] grid, int[][] hits) {
        int m = grid.length, n = grid[0].length, k = hits.length;
        int[][] temp = new int[m][n]; for(int i=0; i<m; i++) temp[i]=grid[i].clone();
        for(int[] h : hits) temp[h[0]][h[1]] = 0;
        int[] p = new int[m*n+1]; for(int i=0; i<=m*n; i++) p[i]=i;
        int[] sz = new int[m*n+1]; for(int i=0; i<=m*n; i++) sz[i]=1;
        for(int i=0; i<m; i++) for(int j=0; j<n; j++) if(temp[i][j]==1) solve(temp, p, sz, i, j);
        int[] res = new int[k];
        for(int i=k-1; i>=0; i--) {
            int r=hits[i][0], c=hits[i][1];
            if(grid[r][c] == 0) continue;
            int prev = sz[find(p, 0)];
            temp[r][c] = 1; solve(temp, p, sz, r, c);
            int curr = sz[find(p, 0)];
            res[i] = Math.max(0, curr - prev - 1);
        }
        return res;
    }
    private void solve(int[][] g, int[] p, int[] sz, int r, int c) {
        int m=g.length, n=g[0].length, curr = r*n+c+1;
        if(r==0) union(p, sz, 0, curr);
        int[] dr={0,0,1,-1}, dc={1,-1,0,0};
        for(int i=0; i<4; i++) {
            int nr=r+dr[i], nc=c+dc[i];
            if(nr>=0 && nr<m && nc>=0 && nc<n && g[nr][nc]==1) union(p, sz, curr, nr*n+nc+1);
        }
    }
    private int find(int[] p, int i) { return p[i]==i?i:(p[i]=find(p, p[i])); }
    private void union(int[] p, int[] sz, int i, int j) { int r1=find(p,i), r2=find(p,j); if(r1!=r2) { p[r1]=r2; sz[r2]+=sz[r1]; } }
}
← Previous QuestionSmallest String With Swaps
Next Question →Redundant Connection II