Bricks Falling When Hit

Hard

#0757Time: O(K * M * N), where K is the number of hits, and M and N are the dimensions of the grid. For each of the K hits, we may traverse the entire grid, leading to a complexity of O(M * N) per hit.Space: O(M * N), where M and N are the dimensions of the grid. This space is used for the `stable` boolean grid and for the recursion stack in the case of DFS.2 companies

Algorithms

Union Find

Data structures

Array Matrix

Companies

Snap Tower Research Capital

Prompt

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] = (row_i, col_i). 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],
 [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.length
n == grid[i].length
1 <= m, n <= 200
grid[i][j] is 0 or 1.
1 <= hits.length <= 4 * 10⁴
hits[i].length == 2
0 <= x_i<= m - 1
0 <= y_i <= n - 1
All (x_i, y_i) are unique.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. For each hit, it removes the specified brick and then re-evaluates the stability of all remaining bricks from scratch by performing a full grid traversal. This is the most straightforward but also the least efficient method.

Algorithm

Initialize an empty result array to store the number of fallen bricks for each hit.
Iterate through each hit in the hits array.
Let (r, c) be the coordinates of the current hit.
If the cell grid[r][c] is already empty (0), it means the hit has no effect. Add 0 to the result and continue to the next hit.
If there is a brick at (r, c), perform the hit by setting grid[r][c] = 0.
After the hit, we need to identify all bricks that are no longer stable and have fallen.
- Create a stable boolean grid of the same dimensions, initialized to false.
- Start a graph traversal (like DFS or BFS) from every brick in the top row (grid[0][j] == 1).
- During the traversal, mark all reachable bricks as true in the stable grid.
Now, count the fallen bricks.
- Initialize a fallen_count to 0.
- Iterate through the entire grid. Any cell (i, j) that contains a brick (grid[i][j] == 1) but is not marked as stable (stable[i][j] == false) is a fallen brick.
- Increment fallen_count for each such brick.
- To ensure the grid state is correct for the next hit, permanently remove these fallen bricks by setting grid[i][j] = 0.
Add the fallen_count to the result array.
After iterating through all hits, return the result array.

Walkthrough

The brute-force method iterates through each hit one by one. For each hit, it first updates the grid by removing the brick at the specified location. Then, it determines the consequences of this removal. To do this, it must find the new set of stable bricks. A brick is stable if it's connected to the top row. We can identify all stable bricks by starting a graph traversal (like DFS or BFS) from every brick in the top row and marking all reachable bricks. After identifying the stable bricks, any remaining brick in the grid is considered unstable and falls. We count these fallen bricks, add the count to our result, and permanently remove them from the grid to set up the state for the next hit. This entire process is repeated for every hit in the input array.

1class Solution {2    public int[] hitBricks(int[][] grid, int[][] hits) {3        int m = grid.length;4        int n = grid[0].length;5        int[] result = new int[hits.length];6 7        for (int i = 0; i < hits.length; i++) {8            int r = hits[i][0];9            int c = hits[i][1];10 11            if (grid[r][c] == 0) {12                result[i] = 0;13                continue;14            }15 16            grid[r][c] = 0; // Perform the hit17 18            // Find all stable bricks after the hit19            boolean[][] stable = new boolean[m][n];20            for (int j = 0; j < n; j++) {21                if (grid[0][j] == 1) {22                    dfs(0, j, grid, stable);23                }24            }25 26            // Count fallen bricks and update the grid27            int fallen = 0;28            for (int row = 0; row < m; row++) {29                for (int col = 0; col < n; col++) {30                    if (grid[row][col] == 1 && !stable[row][col]) {31                        fallen++;32                        grid[row][col] = 0; // Remove fallen brick for next iteration33                    }34                }35            }36            result[i] = fallen;37        }38        return result;39    }40 41    private void dfs(int r, int c, int[][] grid, boolean[][] stable) {42        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 0 || stable[r][c]) {43            return;44        }45        stable[r][c] = true;46        int[] dr = {-1, 1, 0, 0};47        int[] dc = {0, 0, -1, 1};48        for (int i = 0; i < 4; i++) {49            dfs(r + dr[i], c + dc[i], grid, stable);50        }51    }52}

Complexity

Time

O(K * M * N), where K is the number of hits, and M and N are the dimensions of the grid. For each of the K hits, we may traverse the entire grid, leading to a complexity of O(M * N) per hit.

Space

O(M * N), where M and N are the dimensions of the grid. This space is used for the `stable` boolean grid and for the recursion stack in the case of DFS.

Trade-offs

Pros

Simple to understand and implement as it directly models the problem statement.

Cons

Highly inefficient due to its time complexity.
Will result in a 'Time Limit Exceeded' error for larger inputs as it recomputes the stability of the entire grid for every single hit.

This highly efficient approach avoids the costly re-computation of the brute-force method by reversing the problem. Instead of removing bricks and calculating disconnections, we start with the final state (after all hits) and add bricks back one by one in the reverse order of hits. The Union-Find data structure is perfectly suited for this, as it can efficiently track the merging of connected components and their sizes.

Algorithm

Step 1: Mark Hits & Prepare Initial State.
- Modify the input grid in-place. Iterate through the hits array. If a hit (r, c) is on a brick (grid[r][c] == 1), change its value to 2. This marks it as a brick that will be hit later.
- The initial state for our reverse process is a grid containing only the bricks that are never hit (value 1).
Step 2: Initialize Union-Find.
- Create a Union-Find (DSU) data structure with M*N + 1 elements. The elements 0 to M*N - 1 correspond to the grid cells, and the extra element M*N acts as a virtual 'ceiling' node, representing the source of stability.
- Initialize the size array such that size[i] = 1 for grid cells and size[ceiling] = 0.
Step 3: Build Initial Connections.
- Iterate through the grid. For every brick that was never hit (grid[r][c] == 1), connect it to its adjacent non-hit bricks using the union operation.
- If a non-hit brick is in the top row (r == 0), union it with the ceiling node M*N.
- After this step, size[find(ceiling)] gives the number of stable bricks after all hits have occurred.
Step 4: Process Hits in Reverse.
- Create a result array. Iterate through the hits array backwards (from k-1 to 0).
- For each hit (r, c):
  - If grid[r][c] is not 2, it means the hit was on an empty space or a brick that was already removed by a previous hit in the original sequence. The number of fallen bricks is 0. Store this and continue.
  - If grid[r][c] == 2, we are 'adding' this brick back.
  - First, record the number of stable bricks before adding it back: stable_before = size[find(ceiling)].
  - Change grid[r][c] from 2 to 1, effectively adding it to the grid.
  - Union the newly added brick with all its adjacent neighbors (that are now bricks) and with the ceiling node if it's in the top row.
  - After the unions, find the new count of stable bricks: stable_after = size[find(ceiling)].
  - The number of bricks that just became stable by adding this brick is stable_after - stable_before - 1. The -1 accounts for the hit brick itself. This is the number of bricks that fell. Store max(0, stable_after - stable_before - 1) in the result.
Step 5: Return Result.
- The result array is filled in reverse order, so it's already correct. Return it.

Walkthrough

The core insight is that tracking connections (union) is much easier than tracking disconnections (splitting). We can simulate the process in reverse time.

First, we determine the final state of the grid after all hits have occurred. We do this by marking all bricks that will be hit. Then, we initialize a Union-Find data structure representing the grid cells plus a special 'ceiling' node. We build the initial set of connections by uniting all the bricks that survive all the hits. Bricks in the top row are united with the ceiling node, making them stable.

Next, we iterate through the hits array in reverse. For each hit, we 'add' the brick back to the grid. Before adding it, we query the DSU for the current number of stable bricks (the size of the component connected to the ceiling). After adding the brick back (by setting its value to 1 and uniting it with its neighbors and potentially the ceiling), we query the number of stable bricks again. The increase in the stable brick count (minus 1 for the brick we just added) represents the number of other bricks that became stable due to this addition. These are precisely the bricks that must have fallen when this brick was hit in the forward direction. We record this number and proceed to the next hit in reverse, until all hits are processed.

1class Solution {2    private int[] parent;3    private int[] sz; // size of component4    private int m, n;5    private int[][] grid;6    private int[] dr = {0, 1, 0, -1};7    private int[] dc = {1, 0, -1, 0};8 9    public int[] hitBricks(int[][] grid, int[][] hits) {10        this.m = grid.length;11        this.n = grid[0].length;12        this.grid = grid;13        int k = hits.length;14        int[] ans = new int[k];15 16        // Step 1: Mark bricks that will be hit.17        for (int[] hit : hits) {18            if (grid[hit[0]][hit[1]] == 1) {19                grid[hit[0]][hit[1]] = 2; // Mark as a brick to be hit20            }21        }22 23        // Step 2: Initialize DSU.24        int ceiling = m * n;25        parent = new int[m * n + 1];26        sz = new int[m * n + 1];27        for (int i = 0; i < m * n; i++) {28            parent[i] = i;29            sz[i] = 1;30        }31        parent[ceiling] = ceiling;32        sz[ceiling] = 0; // Ceiling node itself is not a brick33 34        // Step 3: Build initial connections from non-hit bricks.35        for (int r = 0; r < m; r++) {36            for (int c = 0; c < n; c++) {37                if (grid[r][c] == 1) {38                    unionNeighbors(r, c);39                }40            }41        }42 43        // Step 4: Process hits in reverse.44        for (int i = k - 1; i >= 0; i--) {45            int r = hits[i][0];46            int c = hits[i][1];47 48            if (grid[r][c] != 2) {49                ans[i] = 0;50            } else {51                int stableBefore = sz[find(ceiling)];52                grid[r][c] = 1; // Add the brick back53                unionNeighbors(r, c);54                int stableAfter = sz[find(ceiling)];55                ans[i] = Math.max(0, stableAfter - stableBefore - 1);56            }57        }58        return ans;59    }60 61    private void unionNeighbors(int r, int c) {62        int idx = r * n + c;63        if (r == 0) {64            union(idx, m * n);65        }66        for (int i = 0; i < 4; i++) {67            int nr = r + dr[i];68            int nc = c + dc[i];69            if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {70                union(idx, nr * n + nc);71            }72        }73    }74 75    private int find(int i) {76        if (parent[i] == i) return i;77        return parent[i] = find(parent[i]);78    }79 80    private void union(int i, int j) {81        int rootI = find(i);82        int rootJ = find(j);83        if (rootI != rootJ) {84            if (sz[rootI] < sz[rootJ]) { // Union by size85                int temp = rootI;86                rootI = rootJ;87                rootJ = temp;88            }89            parent[rootJ] = rootI;90            sz[rootI] += sz[rootJ];91        }92    }93}

Complexity

Time

O((M*N + K) * α(M*N)), where α is the extremely slow-growing Inverse Ackermann function. This is effectively linear time, O(M*N + K), making it very fast.

Space

O(M * N) for the Union-Find data structure's parent and size arrays. The input grid is modified in-place.

Trade-offs

Pros

Very efficient, with a near-linear time complexity.
A standard and powerful technique for dynamic connectivity problems that involve removals.

Cons

More complex to conceptualize and implement compared to the brute-force approach.
The reverse-time logic can be counter-intuitive.

Solutions

Solution

1class Solution {2private3  int[] p;4private5  int[] size;6public7  int[] hitBricks(int[][] grid, int[][] hits) {8    int m = grid.length;9    int n = grid[0].length;10    p = new int[m * n + 1];11    size = new int[m * n + 1];12    for (int i = 0; i < p.length; ++i) {13      p[i] = i;14      size[i] = 1;15    }16    int[][] g = new int[m][n];17    for (int i = 0; i < m; ++i) {18      for (int j = 0; j < n; ++j) {19        g[i][j] = grid[i][j];20      }21    }22    for (int[] h : hits) {23      g[h[0]][h[1]] = 0;24    }25    for (int j = 0; j < n; ++j) {26      if (g[0][j] == 1) {27        union(j, m * n);28      }29    }30    for (int i = 1; i < m; ++i) {31      for (int j = 0; j < n; ++j) {32        if (g[i][j] == 0) {33          continue;34        }35        if (g[i - 1][j] == 1) {36          union(i * n + j, (i - 1) * n + j);37        }38        if (j > 0 && g[i][j - 1] == 1) {39          union(i * n + j, i * n + j - 1);40        }41      }42    }43    int[] ans = new int[hits.length];44    int[] dirs = {-1, 0, 1, 0, -1};45    for (int k = hits.length - 1; k >= 0; --k) {46      int i = hits[k][0];47      int j = hits[k][1];48      if (grid[i][j] == 0) {49        continue;50      }51      g[i][j] = 1;52      int prev = size[find(m * n)];53      if (i == 0) {54        union(j, m * n);55      }56      for (int l = 0; l < 4; ++l) {57        int x = i + dirs[l];58        int y = j + dirs[l + 1];59        if (x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 1) {60          union(i * n + j, x * n + y);61        }62      }63      int curr = size[find(m * n)];64      ans[k] = Math.max(0, curr - prev - 1);65    }66    return ans;67  }68private69  int find(int x) {70    if (p[x] != x) {71      p[x] = find(p[x]);72    }73    return p[x];74  }75private76  void union(int a, int b) {77    int pa = find(a);78    int pb = find(b);79    if (pa != pb) {80      size[pb] += size[pa];81      p[pa] = pb;82    }83  }84}

1class Solution {2public:3  vector<int> p;4  vector<int> size;5  vector<int> hitBricks(vector<vector<int>> &grid, vector<vector<int>> &hits) {6    int m = grid.size(), n = grid[0].size();7    p.resize(m * n + 1);8    size.resize(m * n + 1);9    for (int i = 0; i < p.size(); ++i) {10      p[i] = i;11      size[i] = 1;12    }13    vector<vector<int>> g(m, vector<int>(n));14    for (int i = 0; i < m; ++i)15      for (int j = 0; j < n; ++j)16        g[i][j] = grid[i][j];17    for (auto &h : hits)18      g[h[0]][h[1]] = 0;19    for (int j = 0; j < n; ++j)20      if (g[0][j] == 1)21        merge(j, m * n);22    for (int i = 1; i < m; ++i) {23      for (int j = 0; j < n; ++j) {24        if (g[i][j] == 0)25          continue;26        if (g[i - 1][j] == 1)27          merge(i * n + j, (i - 1) * n + j);28        if (j > 0 && g[i][j - 1] == 1)29          merge(i * n + j, i * n + j - 1);30      }31    }32    vector<int> ans(hits.size());33    vector<int> dirs = {-1, 0, 1, 0, -1};34    for (int k = hits.size() - 1; k >= 0; --k) {35      int i = hits[k][0], j = hits[k][1];36      if (grid[i][j] == 0)37        continue;38      g[i][j] = 1;39      int prev = size[find(m * n)];40      if (i == 0)41        merge(j, m * n);42      for (int l = 0; l < 4; ++l) {43        int x = i + dirs[l], y = j + dirs[l + 1];44        if (x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 1)45          merge(i * n + j, x * n + y);46      }47      int curr = size[find(m * n)];48      ans[k] = max(0, curr - prev - 1);49    }50    return ans;51  }52  int find(int x) {53    if (p[x] != x)54      p[x] = find(p[x]);55    return p[x];56  }57  void merge(int a, int b) {58    int pa = find(a), pb = find(b);59    if (pa != pb) {60      size[pb] += size[pa];61      p[pa] = pb;62    }63  }64};

1class Solution:2    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]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem