LeetCode 803 - Bricks Falling When Hit

LeetCode Problem 803

Difficulty: 🔴 Hard
Topics: Array, Union-Find, Matrix

Solution

Problem Understanding

This problem asks us to simulate a sequence of brick removals in a 2D grid, while determining how many additional bricks become unstable and fall after each removal.

The grid contains only 0 and 1 values:

• 1 represents a brick
• 0 represents an empty cell

A brick is considered stable if it satisfies at least one of these conditions:

1. It is directly connected to the top row
2. It is connected, through adjacent bricks, to another stable brick

Adjacency is four directional, up, down, left, and right.

When a brick is removed by a hit, some surrounding bricks may lose their connection to the top. Any brick that is no longer connected to the top becomes unstable and falls immediately. Fallen bricks disappear permanently.

The important detail is that we only count the bricks that fall because of the removal, not the brick that was directly hit.

For every hit in the hits array, we must return how many bricks fall after that hit is applied.

The constraints are extremely important here:

• Grid size can be up to 200 x 200
• Number of hits can be up to 4 * 10^4

A naive simulation after every hit would be far too slow. Since the grid can contain up to 40,000 cells and there can also be 40,000 hits, we need something much more efficient than recomputing stability from scratch each time.

Several edge cases are especially important:

• A hit may target an already empty cell
• Removing a brick from the top row can destabilize a large connected component
• Multiple hits may disconnect and reconnect regions in complicated ways
• A brick may already have disappeared because of an earlier fall
• The order of operations matters significantly

The key challenge is efficiently tracking which bricks remain connected to the top after each operation.

Approaches

Brute Force Approach

A straightforward approach is to process each hit one by one.

For every hit:

1. Remove the brick
2. Recompute which bricks are stable by performing a BFS or DFS from the top row
3. Any brick not reachable from the top falls
4. Count fallen bricks

This works because a brick is stable exactly when it can reach the top through connected bricks.

However, this approach is extremely expensive.

Suppose:

• There are H hits
• The grid contains M * N cells

For every hit, we may need to scan the entire grid and perform a traversal over all bricks. That leads to:

• O(H * M * N) or worse

With constraints up to 40,000 cells and 40,000 hits, this becomes infeasible.

Optimal Approach, Reverse Processing with Union-Find

The key insight is that removals are difficult to handle dynamically, but additions are much easier.

Union-Find, also called Disjoint Set Union or DSU, is very good at handling connectivity when adding edges or nodes. It is not naturally suited for deletions.

So instead of processing hits forward, we process them backward.

The idea works like this:

1. First, remove every hit brick from the grid
2. Build the connectivity structure for the remaining stable bricks
3. Process hits in reverse order
4. Add each brick back
5. Measure how many new bricks become connected to the top because of that addition

If adding a brick reconnects a disconnected component to the ceiling, then those bricks would have fallen when the brick was originally removed.

This transformation converts a difficult deletion problem into an easier addition problem.

We introduce a special virtual node called the "roof" or "ceiling". Every brick connected to the top row is unioned with this virtual node.

Then:

• The size of the roof component tells us how many stable bricks currently exist
• When adding back a brick, we compare the roof component size before and after
• The increase tells us how many bricks became stable
• We subtract one because the restored brick itself should not be counted as a fallen brick

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(H * M * N)	O(M * N)	Recompute stability after every hit
Optimal	O(M * N + H * α(M * N))	O(M * N)	Reverse processing with Union-Find

Here, α is the inverse Ackermann function, which is effectively constant in practice.

Algorithm Walkthrough

1. Create a copy of the original grid.

We do not want to mutate the original grid directly because we need to know whether a hit originally targeted a brick or an empty cell. 2. Apply all hits to the copied grid.

For every (r, c) in hits:

• If the cell contains a brick, remove it by setting it to 0
• If it is already empty, leave it unchanged

After this step, the grid represents the final state after all hits have been applied. 3. Initialize the Union-Find structure.

We create one node for every grid cell, plus one extra virtual node representing the roof.

If the grid has m * n cells, then:

• Cell index = r * n + c
• Roof index = m * n

4. Build connectivity for the remaining bricks.

Traverse the modified grid.

For every brick:

• If it is in the top row, union it with the roof node
• Union it with adjacent bricks

At this point, the Union-Find structure correctly represents all stable components after every hit has already happened. 5. Process hits in reverse order.

We iterate backward through hits.

For each hit:

• If the original grid had no brick there, append 0

• Otherwise:

• Record the current size of the roof component

• Restore the brick

• Union it with neighboring bricks

• If it is in the top row, union it with the roof

• Record the new roof component size

6. Compute newly stabilized bricks.

Suppose:

• before = roof component size before restoration
• after = roof component size after restoration

Then:

newly_connected = after - before

This includes the restored brick itself, so:

fallen = max(0, newly_connected - 1)

7. Reverse the result array.

Since we processed hits backward, reverse the collected answers before returning them.

Why it works

The critical invariant is that the Union-Find structure always represents the connectivity state after all future hits have already occurred.

When we add a brick back in reverse order, any component that becomes newly connected to the roof must have depended on that brick for stability in the forward direction.

Therefore, the number of newly connected bricks exactly matches the number of bricks that would have fallen when the brick was removed originally.

Python Solution

from typing import List

class UnionFind:
    def __init__(self, size: int):
        self.parent = list(range(size))
        self.component_size = [1] * size

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x: int, y: int) -> None:
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x == root_y:
            return

        if self.component_size[root_x] < self.component_size[root_y]:
            root_x, root_y = root_y, root_x

        self.parent[root_y] = root_x
        self.component_size[root_x] += self.component_size[root_y]

    def size(self, x: int) -> int:
        return self.component_size[self.find(x)]

class Solution:
    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
        rows = len(grid)
        cols = len(grid[0])

        roof = rows * cols

        copied_grid = [row[:] for row in grid]

        for r, c in hits:
            if copied_grid[r][c] == 1:
                copied_grid[r][c] = 0

        uf = UnionFind(rows * cols + 1)

        def index(r: int, c: int) -> int:
            return r * cols + c

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        for r in range(rows):
            for c in range(cols):
                if copied_grid[r][c] == 0:
                    continue

                current = index(r, c)

                if r == 0:
                    uf.union(current, roof)

                for dr, dc in [(1, 0), (0, 1)]:
                    nr = r + dr
                    nc = c + dc

                    if (
                        0 <= nr < rows
                        and 0 <= nc < cols
                        and copied_grid[nr][nc] == 1
                    ):
                        uf.union(current, index(nr, nc))

        result = []

        for r, c in reversed(hits):
            if grid[r][c] == 0:
                result.append(0)
                continue

            before_roof_size = uf.size(roof)

            copied_grid[r][c] = 1
            current = index(r, c)

            if r == 0:
                uf.union(current, roof)

            for dr, dc in directions:
                nr = r + dr
                nc = c + dc

                if (
                    0 <= nr < rows
                    and 0 <= nc < cols
                    and copied_grid[nr][nc] == 1
                ):
                    uf.union(current, index(nr, nc))

            after_roof_size = uf.size(roof)

            fallen_bricks = max(0, after_roof_size - before_roof_size - 1)

            result.append(fallen_bricks)

        return result[::-1]

The implementation begins by defining a Union-Find data structure with path compression and union by size. These optimizations ensure nearly constant time connectivity operations.

The component_size array is especially important because we must efficiently determine how many bricks are connected to the roof at any moment.

The grid is copied before modification so we can distinguish between:

• Cells originally containing bricks
• Cells that were always empty

All hits are first applied to the copied grid. This gives the final grid state after every removal.

The Union-Find structure is then built using the remaining bricks. Every top-row brick is connected to the virtual roof node.

During reverse processing:

• We restore bricks one at a time
• Union them with neighboring bricks
• Measure how many new bricks become connected to the roof

The difference in roof component size tells us exactly how many bricks regain stability.

Finally, we reverse the answer list because the hits were processed backward.

Go Solution

package main

func hitBricks(grid [][]int, hits [][]int) []int {
	rows := len(grid)
	cols := len(grid[0])

	roof := rows * cols

	copiedGrid := make([][]int, rows)
	for r := 0; r < rows; r++ {
		copiedGrid[r] = make([]int, cols)
		copy(copiedGrid[r], grid[r])
	}

	for _, hit := range hits {
		r, c := hit[0], hit[1]
		if copiedGrid[r][c] == 1 {
			copiedGrid[r][c] = 0
		}
	}

	parent := make([]int, rows*cols+1)
	size := make([]int, rows*cols+1)

	for i := range parent {
		parent[i] = i
		size[i] = 1
	}

	var find func(int) int

	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}

	union := func(x, y int) {
		rootX := find(x)
		rootY := find(y)

		if rootX == rootY {
			return
		}

		if size[rootX] < size[rootY] {
			rootX, rootY = rootY, rootX
		}

		parent[rootY] = rootX
		size[rootX] += size[rootY]
	}

	getSize := func(x int) int {
		return size[find(x)]
	}

	index := func(r, c int) int {
		return r*cols + c
	}

	directions := [][]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if copiedGrid[r][c] == 0 {
				continue
			}

			current := index(r, c)

			if r == 0 {
				union(current, roof)
			}

			rightDown := [][]int{
				{1, 0},
				{0, 1},
			}

			for _, dir := range rightDown {
				nr := r + dir[0]
				nc := c + dir[1]

				if nr >= 0 && nr < rows &&
					nc >= 0 && nc < cols &&
					copiedGrid[nr][nc] == 1 {

					union(current, index(nr, nc))
				}
			}
		}
	}

	result := []int{}

	for i := len(hits) - 1; i >= 0; i-- {
		r, c := hits[i][0], hits[i][1]

		if grid[r][c] == 0 {
			result = append(result, 0)
			continue
		}

		before := getSize(roof)

		copiedGrid[r][c] = 1

		current := index(r, c)

		if r == 0 {
			union(current, roof)
		}

		for _, dir := range directions {
			nr := r + dir[0]
			nc := c + dir[1]

			if nr >= 0 && nr < rows &&
				nc >= 0 && nc < cols &&
				copiedGrid[nr][nc] == 1 {

				union(current, index(nr, nc))
			}
		}

		after := getSize(roof)

		fallen := after - before - 1
		if fallen < 0 {
			fallen = 0
		}

		result = append(result, fallen)
	}

	left, right := 0, len(result)-1
	for left < right {
		result[left], result[right] = result[right], result[left]
		left++
		right--
	}

	return result
}

The Go implementation follows the same algorithmic structure as the Python version.

A few Go-specific details are worth noting:

• Slices are used instead of dynamic arrays
• Recursive path compression is implemented in find
• The Union-Find arrays are explicitly initialized
• Grid copying must be done row by row because slices are references
• Result reversal is implemented manually because Go has no built-in reverse helper

Integer overflow is not a concern because the maximum number of cells is only 40,000.

Worked Examples

Example 1

Input:

grid =
[
  [1,0,0,0],
  [1,1,1,0]
]

hits = [[1,0]]

Step 1, Apply All Hits

Remove (1,0):

[
  [1,0,0,0],
  [0,1,1,0]
]

Step 2, Build Union-Find

Only the top-left brick is connected to the roof.

Stable component:

roof <-> (0,0)

The bricks (1,1) and (1,2) are disconnected from the roof.

Step 3, Process Hits in Reverse

Restore (1,0).

Now the grid becomes:

[
  [1,0,0,0],
  [1,1,1,0]
]

Connections formed:

(1,0) <-> (0,0)
(1,0) <-> (1,1)
(1,1) <-> (1,2)

Roof component size increases:

State	Roof Component Size
Before restore	2
After restore	5

Newly connected bricks:

5 - 2 - 1 = 2

Answer:

[2]

Example 2

Input:

grid =
[
  [1,0,0,0],
  [1,1,0,0]
]

hits = [[1,1],[1,0]]

Step 1, Apply All Hits

After both removals:

[
  [1,0,0,0],
  [0,0,0,0]
]

Step 2, Build Initial Connectivity

Only (0,0) remains connected to roof.

Step 3, Reverse Process

Restore (1,0)

Grid:

[
  [1,0,0,0],
  [1,0,0,0]
]

Roof component grows from 2 to 3.

3 - 2 - 1 = 0

No extra bricks stabilized.

Restore (1,1)

Grid:

[
  [1,0,0,0],
  [1,1,0,0]
]

Roof component grows from 3 to 4.

4 - 3 - 1 = 0

Final answer:

[0,0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(M * N + H * α(M * N))	Union-Find operations are nearly constant time
Space	O(M * N)	Parent arrays, component sizes, and copied grid

The grid is traversed a constant number of times, and every union/find operation is amortized nearly constant because of path compression and union by size.

Since α(n) grows extremely slowly, the algorithm is effectively linear for all practical inputs.

Test Cases

from typing import List

def test_solution():
    solution = Solution()

    # Example 1
    assert solution.hitBricks(
        [[1,0,0,0],[1,1,1,0]],
        [[1,0]]
    ) == [2]  # disconnects two bricks

    # Example 2
    assert solution.hitBricks(
        [[1,0,0,0],[1,1,0,0]],
        [[1,1],[1,0]]
    ) == [0,0]  # no additional bricks fall

    # Hit empty cell
    assert solution.hitBricks(
        [[1]],
        [[0,0]]
    ) == [0]  # removing only brick causes no extra fall

    # Single brick not on top
    assert solution.hitBricks(
        [[0],[1]],
        [[1,0]]
    ) == [0]  # brick already unstable

    # Entire component falls
    assert solution.hitBricks(
        [[1,1,1],
         [0,1,0],
         [0,1,0]],
        [[0,1]]
    ) == [3]  # removing top connector drops chain

    # Multiple hits
    assert solution.hitBricks(
        [[1,1,1],
         [1,0,1],
         [1,1,1]],
        [[1,0],[0,1]]
    ) == [0,5]  # second hit disconnects large region

    # No bricks
    assert solution.hitBricks(
        [[0,0],[0,0]],
        [[0,0]]
    ) == [0]  # nothing to remove

    # Large stable block
    assert solution.hitBricks(
        [[1,1],
         [1,1]],
        [[1,1]]
    ) == [0]  # remaining bricks still connected

    # Disconnect center
    assert solution.hitBricks(
        [[1,1,1],
         [1,1,1],
         [1,1,1]],
        [[1,1]]
    ) == [0]  # alternate paths preserve stability

test_solution()

Test Summary

Test	Why
Example 1	Verifies cascading fall behavior
Example 2	Verifies no unnecessary falls
Hit empty cell	Ensures empty hits return zero
Single unstable brick	Tests already disconnected brick
Entire component falls	Validates large cascading disconnect
Multiple hits	Ensures reverse processing correctness
No bricks	Tests empty grid handling
Large stable block	Verifies alternate stable paths
Disconnect center	Ensures connectivity redundancy works

Edge Cases

One important edge case occurs when a hit targets an already empty cell. A naive implementation might accidentally restore a brick during reverse processing even though no brick originally existed there. This implementation avoids that bug by checking the original grid before restoration. If the original cell was 0, the answer is immediately 0.

Another critical edge case involves bricks that are not connected to the top even before a hit occurs. Such bricks are already unstable conceptually, although they remain present until affected. The reverse Union-Find approach naturally handles this because only bricks connected to the roof belong to the stable component. Disconnected bricks never contribute to roof size changes.

A particularly tricky scenario occurs when multiple paths connect a component to the roof. Removing one brick may appear significant but still leave an alternate stable path. A DFS-based simulation can easily mishandle this if connectivity is not recomputed correctly. The Union-Find structure handles this naturally because connectivity is represented globally, not locally.

Another subtle case is when a top-row brick is restored during reverse processing. Such bricks must immediately connect to the virtual roof node. Forgetting this step causes all downstream stability calculations to become incorrect. The implementation explicitly unions every top-row brick with the roof during both initialization and restoration.