Watch 9 video solutions for Bricks Falling When Hit, a hard level problem involving Array, Union Find, Matrix. This walkthrough by Hua Hua has 5,812 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 Overview: You are given a grid of bricks where 1 represents a brick and 0 represents empty space. Each hit removes a brick, and bricks that are no longer connected to the top row fall. After every hit, return how many bricks drop due to the loss of stability.
Approach 1: BFS for Stability Detection (O(k * m * n) time, O(m * n) space)
This direct simulation approach processes hits in the given order. After removing a brick, run a BFS or DFS from the top row to mark all stable bricks that remain connected to the "roof." Any brick not visited during this traversal is unstable and must fall. The algorithm repeatedly scans the matrix and performs BFS, which makes it simple to implement but expensive when the grid is large or the number of hits is high.
Approach 2: Reverse Simulation and Union-Find (O((m * n + k) α(n)) time, O(m * n) space)
The key insight: instead of simulating bricks falling forward, process hits in reverse. First remove all hit bricks from the grid. Build a Union-Find structure connecting remaining bricks, plus a virtual "roof" node representing the top row. Then add bricks back one by one in reverse hit order. Each addition unions the brick with adjacent bricks in the grid. By comparing the size of the roof-connected component before and after the union operations, you determine how many previously unstable bricks become stable again. That difference (minus the brick just added) equals the number that would have fallen in forward time.
Approach 3: Union-Find with Reverse Hits (Optimized Roof Tracking) (O((m * n + k) α(n)) time, O(m * n) space)
This is the optimized production solution used in most editorial implementations. A Union-Find structure tracks connected components and their sizes, with a special root representing the ceiling. After removing all hit bricks initially, union all adjacent bricks. While restoring hits in reverse order, connect the restored brick to its valid neighbors and possibly the roof. The change in the roof component size directly reveals how many bricks regained stability. Path compression and union-by-rank keep operations nearly constant time.
Recommended for interviews: Interviewers expect the reverse simulation with Union-Find approach. The BFS simulation demonstrates understanding of stability and connectivity, but it does not scale. The Union-Find reverse strategy shows you recognize that forward simulation is expensive and that processing events backward transforms the problem into incremental connectivity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS Stability Detection | O(k * m * n) | O(m * n) | Useful for understanding the stability rule or when constraints are small |
| Reverse Simulation + Union-Find | O((m*n + k) α(n)) | O(m * n) | Efficient solution for large grids and many hits |
| Union-Find with Reverse Hits | O((m*n + k) α(n)) | O(m * n) | Preferred interview and production approach with optimal performance |