Bricks falling when hit

Array Union-Find Matrix

36.9% acceptance

Feb 22, 2026

1202

192

You are given an m x n binary grid, where each 1 represents a brick and 0 represents an empty space. A brick is stable if: It is directly connected to the top of the grid, or At least one other brick in its four adjacent cells is stable. You are also given an array hits, which is a sequence of erasures we want to apply. Each time we want to erase the brick at the location hits[i] = (rowi, coli). The brick on that location (if it exists) will disappear. Some other bricks may no longer be stable because of that erasure and will fall. Once a brick falls, it is immediately erased from the grid (i.e., it does not land on other stable bricks). Return an array result, where each result[i] is the number of bricks that will fall after the ith erasure is applied. Note that an erasure may refer to a location with no brick, and if it does, no bricks drop.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn hit_bricks(grid: Vec<Vec<i32>>, hits: Vec<Vec<i32>>) -> Vec<i32> {
    let rows = grid.len();
    let cols = grid[0].len();
    let mut g = grid.clone();
    // Remove all hit bricks
    for h in &hits { g[h[0] as usize][h[1] as usize] = 0; }
    // Union-Find with extra node = rows*cols as "roof"
    let sz = rows * cols + 1;
    let roof = rows * cols;
    let mut parent: Vec<usize> = (0..sz).collect();
    let mut size = vec![1usize; sz];
    fn find(p: &mut Vec<usize>, mut x: usize) -> usize {
      while p[x] != x { p[x] = p[p[x]]; x = p[x]; }
      x
    }
    fn union(p: &mut Vec<usize>, s: &mut Vec<usize>, a: usize, b: usize) {
      let (ra, rb) = (find(p, a), find(p, b));
      if ra == rb { return; }
      if s[ra] < s[rb] { p[ra] = rb; s[rb] += s[ra]; }
      else { p[rb] = ra; s[ra] += s[rb]; }
    }
    let idx = |r: usize, c: usize| r * cols + c;
    // Build initial state with removed hits
    for r in 0..rows {
      for c in 0..cols {
        if g[r][c] == 1 {
          if r == 0 { union(&mut parent, &mut size, idx(r,c), roof); }
          if r > 0 && g[r-1][c] == 1 { union(&mut parent, &mut size, idx(r,c), idx(r-1,c)); }
          if c > 0 && g[r][c-1] == 1 { union(&mut parent, &mut size, idx(r,c), idx(r,c-1)); }
        }
      }
    }
    let mut result = vec![0i32; hits.len()];
    let dirs: [(i32,i32);4] = [(0,1),(0,-1),(1,0),(-1,0)];
    for i in (0..hits.len()).rev() {
      let (r, c) = (hits[i][0] as usize, hits[i][1] as usize);
      if grid[r][c] == 0 { continue; } // no brick here originally
      let prev = find(&mut parent, roof);
      let prev_roof_size = size[prev];
      g[r][c] = 1;
      if r == 0 { union(&mut parent, &mut size, idx(r,c), roof); }
      for (dr, dc) in dirs {
        let nr = r as i32 + dr;
        let nc = c as i32 + dc;
        if nr >= 0 && nr < rows as i32 && nc >= 0 && nc < cols as i32 {
          let (nr, nc) = (nr as usize, nc as usize);
          if g[nr][nc] == 1 { union(&mut parent, &mut size, idx(r,c), idx(nr,nc)); }
        }
      }
      let new_roof_size = size[find(&mut parent, roof)];
      result[i] = (new_roof_size as i32 - prev_roof_size as i32 - 1).max(0);
    }
    result

  }
}