Bricks Falling When Hit

In the Bricks Falling When Hit problem, you need to simulate the effect of erasing bricks sequentially in a grid. Use a combination of Union Find and Array techniques to track how bricks fall after each hit. The key challenge is handling the stability of bricks efficiently after each modification.

Problem Statement

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 row or has at least one neighboring brick that is stable. You will also be given an array hits, which contains the sequence of positions where bricks will be erased. After each erasure, some bricks may no longer be stable and will fall.

Your goal is to return an array where each element represents the number of bricks that fall after the ith erasure is applied. This requires simulating the erasure process and determining how the stability of other bricks is affected by each hit. The key to solving this problem efficiently is utilizing Union Find to manage connectivity between bricks.

Examples

Example 1

Input: grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]

Output: [2]

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]

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 * 104
• hits[i].length == 2
• 0 <= xi <= m - 1
• 0 <= yi <= n - 1
• All (xi, yi) are unique.

Solution Approach

Union Find Setup

The problem requires us to track the stability of bricks after each hit. A Union Find (disjoint-set) structure helps efficiently determine which bricks are connected to the top row and, consequently, which bricks are stable. By initially marking all positions in the grid, we can then progressively simulate each erasure and determine which bricks fall.

Reversing Hits for Initial Stability

To handle the erasures efficiently, we reverse the sequence of hits and simulate the effect of all hits applied before determining the result. This allows us to restore the grid to its original state, then check how the removal of bricks at each step affects the stability of other bricks connected to the top row.

Tracking Falling Bricks

For each hit, after restoring the grid, we use Union Find to check which bricks are still connected to the top row and which ones will fall. Once a brick is identified as falling, it is immediately erased, and this process continues until no further changes occur.

Complexity Analysis

Metric	Value
Time	O(N \cdot \alpha(N))
Space	O(N)

The time complexity is O(N * α(N)), where N is the total number of cells in the grid and α(N) is the inverse Ackermann function, which grows very slowly. The space complexity is O(N), where N is the number of grid cells and the size of the Union Find structure.

What Interviewers Usually Probe

• Tests the candidate's ability to handle grid manipulation using efficient data structures like Union Find.
• Assesses the candidate's understanding of graph connectivity and the impact of sequential modifications on data structures.
• Evaluates the candidate's approach to problem-solving under constraints like time complexity and handling large inputs.

Common Pitfalls or Variants

Common pitfalls

• Forgetting to reverse the hits and restoring the grid before processing each hit.
• Mismanaging the Union Find structure, leading to incorrect connectivity checks.
• Overcomplicating the problem by using brute force instead of efficient Union Find operations.

Follow-up variants

• What if the grid was dynamic and cells could be added after each erasure?
• How would you approach this if you were required to support a 3D grid?
• Can this be optimized further for very large grids, say for a billion cells?

FAQ

How do I solve Bricks Falling When Hit using Union Find?

You need to simulate the erasure of bricks while tracking the stability of others using Union Find. Start by reversing the hits and restoring the grid before applying each hit.

What is the time complexity of the Bricks Falling When Hit problem?

The time complexity is O(N * α(N)), where N is the number of cells in the grid and α(N) is the inverse Ackermann function.

How can I handle multiple hits in the Bricks Falling When Hit problem?

You can process the hits in reverse order, restoring the grid at each step, and then using Union Find to determine the number of falling bricks after each hit.

What happens if a brick is no longer stable after a hit?

If a brick is no longer stable after a hit, it falls and is erased from the grid immediately, affecting the stability of other connected bricks.

How does GhostInterview assist with solving Bricks Falling When Hit?

GhostInterview offers real-time feedback and helps you optimize your Union Find approach, providing detailed explanations to avoid common pitfalls and improve your solution.