Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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:
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.
Example 1:
Input: grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]] Output: [2] Explanation: Starting with the grid: [[1,0,0,0], [1,1,1,0]] We erase the underlined brick at (1,0), resulting in the grid: [[1,0,0,0], [0,1,1,0]] The two underlined bricks are no longer stable as they are no longer connected to the top nor adjacent to another stable brick, so they will fall. The resulting grid is: [[1,0,0,0], [0,0,0,0]] Hence the result is [2].
Example 2:
Input: grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]] Output: [0,0] Explanation: Starting with the grid: [[1,0,0,0], [1,1,0,0]] We erase the underlined brick at (1,1), resulting in the grid: [[1,0,0,0], [1,0,0,0]] All remaining bricks are still stable, so no bricks fall. The grid remains the same: [[1,0,0,0], [1,0,0,0]] Next, we erase the underlined brick at (1,0), resulting in the grid: [[1,0,0,0], [0,0,0,0]] Once again, all remaining bricks are still stable, so no bricks fall. Hence the result is [0,0].
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 200grid[i][j] is 0 or 1.1 <= hits.length <= 4 * 104hits[i].length == 20 <= xi <= m - 10 <= yi <= n - 1(xi, yi) are unique.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Union-Find
[[1,0,0,0],[1,1,1,0]] [[1,0]]
[[1,0,0,0],[1,1,0,0]] [[1,1],[1,0]]
last-day-where-you-can-still-cross)number-of-ways-to-build-sturdy-brick-wall)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #803: Bricks Falling When Hit
class Solution {
private int[] p;
private int[] size;
public int[] hitBricks(int[][] grid, int[][] hits) {
int m = grid.length;
int n = grid[0].length;
p = new int[m * n + 1];
size = new int[m * n + 1];
for (int i = 0; i < p.length; ++i) {
p[i] = i;
size[i] = 1;
}
int[][] g = new int[m][n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
g[i][j] = grid[i][j];
}
}
for (int[] h : hits) {
g[h[0]][h[1]] = 0;
}
for (int j = 0; j < n; ++j) {
if (g[0][j] == 1) {
union(j, m * n);
}
}
for (int i = 1; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (g[i][j] == 0) {
continue;
}
if (g[i - 1][j] == 1) {
union(i * n + j, (i - 1) * n + j);
}
if (j > 0 && g[i][j - 1] == 1) {
union(i * n + j, i * n + j - 1);
}
}
}
int[] ans = new int[hits.length];
int[] dirs = {-1, 0, 1, 0, -1};
for (int k = hits.length - 1; k >= 0; --k) {
int i = hits[k][0];
int j = hits[k][1];
if (grid[i][j] == 0) {
continue;
}
g[i][j] = 1;
int prev = size[find(m * n)];
if (i == 0) {
union(j, m * n);
}
for (int l = 0; l < 4; ++l) {
int x = i + dirs[l];
int y = j + dirs[l + 1];
if (x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 1) {
union(i * n + j, x * n + y);
}
}
int curr = size[find(m * n)];
ans[k] = Math.max(0, curr - prev - 1);
}
return ans;
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
private void union(int a, int b) {
int pa = find(a);
int pb = find(b);
if (pa != pb) {
size[pb] += size[pa];
p[pa] = pb;
}
}
}
// Accepted solution for LeetCode #803: Bricks Falling When Hit
func hitBricks(grid [][]int, hits [][]int) []int {
m, n := len(grid), len(grid[0])
p := make([]int, m*n+1)
size := make([]int, len(p))
for i := range p {
p[i] = i
size[i] = 1
}
var find func(x int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
union := func(a, b int) {
pa, pb := find(a), find(b)
if pa != pb {
size[pb] += size[pa]
p[pa] = pb
}
}
g := make([][]int, m)
for i := range g {
g[i] = make([]int, n)
for j := range g[i] {
g[i][j] = grid[i][j]
}
}
for _, h := range hits {
g[h[0]][h[1]] = 0
}
for j, v := range g[0] {
if v == 1 {
union(j, m*n)
}
}
for i := 1; i < m; i++ {
for j := 0; j < n; j++ {
if g[i][j] == 0 {
continue
}
if g[i-1][j] == 1 {
union(i*n+j, (i-1)*n+j)
}
if j > 0 && g[i][j-1] == 1 {
union(i*n+j, i*n+j-1)
}
}
}
ans := make([]int, len(hits))
dirs := []int{-1, 0, 1, 0, -1}
for k := len(hits) - 1; k >= 0; k-- {
i, j := hits[k][0], hits[k][1]
if grid[i][j] == 0 {
continue
}
g[i][j] = 1
prev := size[find(m*n)]
if i == 0 {
union(j, m*n)
}
for l := 0; l < 4; l++ {
x, y := i+dirs[l], j+dirs[l+1]
if x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 1 {
union(i*n+j, x*n+y)
}
}
curr := size[find(m*n)]
ans[k] = max(0, curr-prev-1)
}
return ans
}
# Accepted solution for LeetCode #803: Bricks Falling When Hit
class Solution:
def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
def union(a, b):
pa, pb = find(a), find(b)
if pa != pb:
size[pb] += size[pa]
p[pa] = pb
m, n = len(grid), len(grid[0])
p = list(range(m * n + 1))
size = [1] * len(p)
g = deepcopy(grid)
for i, j in hits:
g[i][j] = 0
for j in range(n):
if g[0][j] == 1:
union(j, m * n)
for i in range(1, m):
for j in range(n):
if g[i][j] == 0:
continue
if g[i - 1][j] == 1:
union(i * n + j, (i - 1) * n + j)
if j > 0 and g[i][j - 1] == 1:
union(i * n + j, i * n + j - 1)
ans = []
for i, j in hits[::-1]:
if grid[i][j] == 0:
ans.append(0)
continue
g[i][j] = 1
prev = size[find(m * n)]
if i == 0:
union(j, m * n)
for a, b in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and g[x][y] == 1:
union(i * n + j, x * n + y)
curr = size[find(m * n)]
ans.append(max(0, curr - prev - 1))
return ans[::-1]
// Accepted solution for LeetCode #803: Bricks Falling When Hit
/**
* [0803] Bricks Falling When Hit
*
* 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 i^th erasure is applied.
* Note that an erasure may refer to a location with no brick, and if it does, no bricks drop.
*
* Example 1:
*
* Input: grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
* Output: [2]
* Explanation: Starting with the grid:
* [[1,0,0,0],
* [<u>1</u>,1,1,0]]
* We erase the underlined brick at (1,0), resulting in the grid:
* [[1,0,0,0],
* [0,<u>1</u>,<u>1</u>,0]]
* The two underlined bricks are no longer stable as they are no longer connected to the top nor adjacent to another stable brick, so they will fall. The resulting grid is:
* [[1,0,0,0],
* [0,0,0,0]]
* Hence the result is [2].
*
* Example 2:
*
* Input: grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
* Output: [0,0]
* Explanation: Starting with the grid:
* [[1,0,0,0],
* [1,<u>1</u>,0,0]]
* We erase the underlined brick at (1,1), resulting in the grid:
* [[1,0,0,0],
* [1,0,0,0]]
* All remaining bricks are still stable, so no bricks fall. The grid remains the same:
* [[1,0,0,0],
* [<u>1</u>,0,0,0]]
* Next, we erase the underlined brick at (1,0), resulting in the grid:
* [[1,0,0,0],
* [0,0,0,0]]
* Once again, all remaining bricks are still stable, so no bricks fall.
* Hence the result is [0,0].
*
*
* 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.
*
*/
pub struct Solution {}
// problem: https://leetcode.com/problems/bricks-falling-when-hit/
// discuss: https://leetcode.com/problems/bricks-falling-when-hit/discuss/?currentPage=1&orderBy=most_votes&query=
// submission codes start here
impl Solution {
// Credit: https://leetcode.com/problems/bricks-falling-when-hit/discuss/2252748/Rust-Union-Find
const DIRS: &'static [isize] = &[0, -1, 0, 1, 0];
pub fn hit_bricks(grid: Vec<Vec<i32>>, hits: Vec<Vec<i32>>) -> Vec<i32> {
let len_rs: usize = grid.len();
let len_cs: usize = grid[0].len();
let len_ns: usize = len_rs * len_cs;
let len_hs: usize = hits.len();
let mut grid: Vec<Vec<i32>> = {
let mut grid = grid;
for hit in &hits {
let r: usize = hit[0] as usize;
let c: usize = hit[1] as usize;
if grid[r][c] == 1 {
grid[r][c] = 2;
}
}
grid
};
let mut roots: Vec<usize> = (0..len_ns + 1).collect();
let mut sizes: Vec<i32> = vec![1; len_ns + 1];
for r in 0..len_rs {
for c in 0..len_cs {
if grid[r][c] == 1 {
Self::union_around((r, c), &grid, &mut roots, &mut sizes);
}
}
}
let mut bricks_left = sizes[Self::find(0, &mut roots)];
let mut bricks_dropped: Vec<i32> = vec![0; len_hs];
for (idx, hit) in hits.iter().enumerate().rev() {
let r: usize = hit[0] as usize;
let c: usize = hit[1] as usize;
if grid[r][c] == 2 {
grid[r][c] = 1;
Self::union_around((r, c), &grid, &mut roots, &mut sizes);
let cur_bricks_left = sizes[Self::find(0, &mut roots)];
bricks_dropped[idx] = if cur_bricks_left == bricks_left {
0
} else {
cur_bricks_left - bricks_left - 1
};
bricks_left = cur_bricks_left;
}
}
bricks_dropped
}
fn union_around(
coord: (usize, usize),
grid: &Vec<Vec<i32>>,
roots: &mut Vec<usize>,
sizes: &mut Vec<i32>,
) {
let len_rs: usize = grid.len();
let len_cs: usize = grid[0].len();
let (r, c) = coord;
for d in 0..4 {
let r_nxt: isize = r as isize + Self::DIRS[d];
let c_nxt: isize = c as isize + Self::DIRS[d + 1];
if r_nxt < 0
|| c_nxt < 0
|| r_nxt as usize >= len_rs
|| c_nxt as usize >= len_cs
|| grid[r_nxt as usize][c_nxt as usize] != 1
{
continue;
}
Self::union(
Self::hash(r, c, len_cs),
Self::hash(r_nxt as usize, c_nxt as usize, len_cs),
roots,
sizes,
);
}
if r == 0 {
Self::union(0, Self::hash(r, c, len_cs), roots, sizes);
}
}
fn union(x: usize, y: usize, roots: &mut Vec<usize>, sizes: &mut Vec<i32>) {
let root_x: usize = Self::find(x, roots);
let root_y: usize = Self::find(y, roots);
if root_x == root_y {
return;
}
if sizes[root_x] > sizes[root_y] {
roots[root_y] = root_x;
sizes[root_x] += sizes[root_y];
sizes[root_y] = 0;
} else {
roots[root_x] = root_y;
sizes[root_y] += sizes[root_x];
sizes[root_x] = 0;
}
}
fn find(mut x: usize, roots: &mut Vec<usize>) -> usize {
while x != roots[x] {
roots[x] = roots[roots[x]];
x = roots[x];
}
x
}
fn hash(r: usize, c: usize, len_cs: usize) -> usize {
r * len_cs + c + 1
}
}
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_0803_example_1() {
let grid = vec![vec![1, 0, 0, 0], vec![1, 1, 1, 0]];
let hits = vec![vec![1, 0]];
let result = vec![2];
assert_eq!(Solution::hit_bricks(grid, hits), result);
}
#[test]
fn test_0803_example_2() {
let grid = vec![vec![1, 0, 0, 0], vec![1, 1, 0, 0]];
let hits = vec![vec![1, 1], vec![1, 0]];
let result = vec![0, 0];
assert_eq!(Solution::hit_bricks(grid, hits), result);
}
}
// Accepted solution for LeetCode #803: Bricks Falling When Hit
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #803: Bricks Falling When Hit
// class Solution {
// private int[] p;
// private int[] size;
//
// public int[] hitBricks(int[][] grid, int[][] hits) {
// int m = grid.length;
// int n = grid[0].length;
// p = new int[m * n + 1];
// size = new int[m * n + 1];
// for (int i = 0; i < p.length; ++i) {
// p[i] = i;
// size[i] = 1;
// }
// int[][] g = new int[m][n];
// for (int i = 0; i < m; ++i) {
// for (int j = 0; j < n; ++j) {
// g[i][j] = grid[i][j];
// }
// }
// for (int[] h : hits) {
// g[h[0]][h[1]] = 0;
// }
// for (int j = 0; j < n; ++j) {
// if (g[0][j] == 1) {
// union(j, m * n);
// }
// }
// for (int i = 1; i < m; ++i) {
// for (int j = 0; j < n; ++j) {
// if (g[i][j] == 0) {
// continue;
// }
// if (g[i - 1][j] == 1) {
// union(i * n + j, (i - 1) * n + j);
// }
// if (j > 0 && g[i][j - 1] == 1) {
// union(i * n + j, i * n + j - 1);
// }
// }
// }
// int[] ans = new int[hits.length];
// int[] dirs = {-1, 0, 1, 0, -1};
// for (int k = hits.length - 1; k >= 0; --k) {
// int i = hits[k][0];
// int j = hits[k][1];
// if (grid[i][j] == 0) {
// continue;
// }
// g[i][j] = 1;
// int prev = size[find(m * n)];
// if (i == 0) {
// union(j, m * n);
// }
// for (int l = 0; l < 4; ++l) {
// int x = i + dirs[l];
// int y = j + dirs[l + 1];
// if (x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 1) {
// union(i * n + j, x * n + y);
// }
// }
// int curr = size[find(m * n)];
// ans[k] = Math.max(0, curr - prev - 1);
// }
// return ans;
// }
//
// private int find(int x) {
// if (p[x] != x) {
// p[x] = find(p[x]);
// }
// return p[x];
// }
//
// private void union(int a, int b) {
// int pa = find(a);
// int pb = find(b);
// if (pa != pb) {
// size[pb] += size[pa];
// p[pa] = pb;
// }
// }
// }
Use this to step through a reusable interview workflow for this problem.
Track components with a list or adjacency matrix. Each union operation may need to update all n elements’ component labels, giving O(n) per union. For n union operations total: O(n²). Find is O(1) with direct lookup, but union dominates.
With path compression and union by rank, each find/union operation takes O(α(n)) amortized time, where α is the inverse Ackermann function — effectively constant. Space is O(n) for the parent and rank arrays. For m operations on n elements: O(m × α(n)) total.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.