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.
This approach involves processing the hits in reverse order and leveraging a union-find data structure to efficiently manage brick connectivity. The idea is to treat the grid by marking each brick in the grid as destroyed first (based on the hits) and then process each hit in reverse order, restoring the brick back in the grid. If restoring a brick causes previously unstable bricks to stabilize (due to reconnection to the top), then count these bricks as 'falling' during the original 'hit' sequence.
This Python solution constructs a union-find data structure to manage connectivity among bricks. Grid cells are treated as nodes, with an additional node representing the 'top row'. The union-find structure allows for dynamic connectivity management as bricks are restored in reverse of the original hits. When a brick is restored, we check which bricks it makes stable (union to the top), counting the difference in connected components size to determine the number of stabilized bricks.
Python
Time Complexity: O((m * n) + h * alpha(m * n)), where h is the number of hits, and alpha is the inverse Ackermann function for path compression in union-find. Space Complexity: O(m * n) for the union-find structure.
This alternative approach involves using Breadth-First Search (BFS) to identify and maintain stability information within the grid. After simulating the hits by removing the corresponding bricks from the grid, iterate through each cell that remains, performing BFS to determine which bricks are stable by connecting them to the top row directly or indirectly. Calculate how many become unstable after each hit in reverse.
This Python solution employs BFS to identify which bricks remain stable, starting from restoration of each hit. It computes which bricks remain unvisited (unstable) after reintroducing each brick in 'hits' order. Stones connected to the top, directly or indirectly, are stable. After each restoration, it checks all potential connections, only considering valid and new stable bricks.
Python
Time Complexity: O((m * n) * (h + 1)), for grid exploration per hit in worst BFS case. Space Complexity: O(m * n) for visited grid and auxiliary data.
The Union-Find algorithm, also known as Disjoint Set Union (DSU), is used to manage a collection of disjoint (non-overlapping) sets. In this approach, we treat each brick as a node in a graph, and two bricks are connected if they are adjacent.
The key insight here is that the process of removing a brick and causing others to fall can be reversed by processing the hits in reverse order. Essentially, we 'add' bricks instead and track when they become stable using the Union-Find structure.
By processing in reverse, every time a brick is re-added, we can check its impact on other previously disconnected bricks and accurately determine how many fall (or in this reverse logic, how many become stable).
This solution employs a Union-Find data structure to manage sets of connected bricks and a reverse approach for hit processing. Initially, bricks are marked and connections established to represent already stable bricks.
By iterating reversely over the hits, each 'removed' brick (in original operation) is revisited, and its stabilization impact is calculated by observing changes in the count of bricks connected to the top.
Time Complexity: O((m * n) + h), where m is the number of rows, n is the number of columns, and h is the number of hits, as each operation finds or unions amortized over time.
Space Complexity: O(m * n), mainly due to the Union-Find structure.
| Approach | Complexity |
|---|---|
| Approach using Reverse Simulation and Union-Find | Time Complexity: O((m * n) + h * alpha(m * n)), where h is the number of hits, and alpha is the inverse Ackermann function for path compression in union-find. Space Complexity: O(m * n) for the union-find structure. |
| Approach using BFS for Stability Detection | Time Complexity: O((m * n) * (h + 1)), for grid exploration per hit in worst BFS case. Space Complexity: O(m * n) for visited grid and auxiliary data. |
| Union-Find with Reverse Hits | Time Complexity: O((m * n) + h), where m is the number of rows, n is the number of columns, and h is the number of hits, as each operation finds or unions amortized over time. |
| Default Approach | — |
| 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 |
花花酱 LeetCode 803. Bricks Falling When Hit - 刷题找工作 EP175 • Hua Hua • 5,812 views views
Watch 8 more video solutions →Practice Bricks Falling When Hit with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor