Bricks Falling When Hit - Solution & Explanation

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.

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.

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.

• First, process the grid and hits in reverse to determine which bricks would remain after all hits.
• Use a Union-Find structure to track stable bricks, i.e., bricks connected to the top row.
• Iterate over hits in reverse, 'adding' each brick back and updating the union-find structure to check if it stabilizes others.

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.