Bricks Falling When Hit

Problem Statement

In this task, you are presented with a two-dimensional binary grid representing a section of a wall, where 1s represent bricks and 0s represent empty spaces. The stability of each brick is determined by its vertical or horizontal connection to other stable bricks, or its direct attachment to the wall's top edge. The challenge involves simulating the effect of sequentially erasing specific bricks as specified in a list hits. Each entry in hits details the position of a brick to be erased, potentially destabilizing other bricks which might then fall. Once a brick falls, it is removed from the grid immediately for subsequent operations. The main objective is to compute and return an array, where each entry corresponds to the number of bricks that fall due to each specified erasure in hits. Importantly, some erasures might target positions where no brick is present, resulting in no bricks falling.

Examples

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

Approach and Intuition

Given the dynamical nature of the problem where bricks can affect the stability of neighboring ones, an efficient approach must address how each erasure propagates changes through the grid. Understanding and solving it involves the following key steps:

1. Initial Stability Assessment:

   • Before processing any hits, determine which bricks are initially stable by checking their connection to the top row or to any stable neighboring bricks.

2. Reverse Simulation:

   • To effectively account for each erasure's impact, consider simulating the erasures in reverse. Start by marking the bricks to be hit (so they're ignored or treated as if they're already deleted) and assess the stability of the structure without these elements.
   • Then, reintroduce each "hit" brick one by one (in reverse order) and observe the re-stabilization effects.

3. Connectivity Tracking:

   • Utilize a data structure like the Union-Find (or union by rank and path compression) to keep track of connected components of bricks efficiently. This helps quickly determine the size of the fallout when the connected structure is disrupted.

4. Propagating Erasures:

   • For each erasure, calculate how many connected bricks fall by checking how connectivity changes when a brick is removed. If deletion of a brick causes a separation in the Union-Find, the size of the new part (if any) that doesn't have top row connectivity represents the number of bricks that will fall.

5. Accumulating Results:

   • For each hit processed, append the computed number of falling bricks to the resulting list.

This approach efficiently handles brick stability and updates connectivity, making it suitable for large grids and multiple erasures, staying within performance constraints. Each hit's effect on grid stability is captured accurately implicating the correct count of bricks that would fall.

Solutions

class Solver {
    public int[] processHits(int[][] matrix, int[][] operations) {
        int rows = matrix.length, cols = matrix[0].length;
        int[] deltaRow = {1, 0, -1, 0};
        int[] deltaCol = {0, 1, 0, -1};

        int[][] tempGrid = new int[rows][cols];
        for (int r = 0; r < rows; r++)
            tempGrid[r] = matrix[r].clone();
        for (int[] hit : operations)
            tempGrid[hit[0]][hit[1]] = 0;

        UnionFind uf = new UnionFind(rows * cols + 1);
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (tempGrid[r][c] == 1) {
                    int pos = r * cols + c;
                    if (r == 0)
                        uf.union(pos, rows * cols);
                    if (r > 0 && tempGrid[r - 1][c] == 1)
                        uf.union(pos, (r - 1) * cols + c);
                    if (c > 0 && tempGrid[r][c - 1] == 1)
                        uf.union(pos, r * cols + c - 1);
                }
            }
        }
        int count = operations.length;
        int[] output = new int[count--];

        while (count >= 0) {
            int r = operations[count][0];
            int c = operations[count][1];
            int beforeSize = uf.rooftop();
            if (matrix[r][c] == 0) {
                count--;
            } else {
                int idx = r * cols + c;
                for (int k = 0; k < 4; ++k) {
                    int nr = r + deltaRow[k];
                    int nc = c + deltaCol[k];
                    if (0 <= nr && nr < rows && 0 <= nc && nc < cols && tempGrid[nr][nc] == 1)
                        uf.union(idx, nr * cols + nc);
                }
                if (r == 0)
                    uf.union(idx, rows * cols);
                tempGrid[r][c] = 1;
                output[count--] = Math.max(0, uf.rooftop() - beforeSize - 1);
            }
        }

        return output;
    }
}

class UnionFind {
    int[] parent;
    int[] depth;
    int[] size;

    public UnionFind(int size) {
        parent = new int[size];
        for (int i = 0; i < size; ++i)
            parent[i] = i;
        depth = new int[size];
        this.size = new int[size];
        Arrays.fill(this.size, 1);
    }

    public int find(int node) {
        if (parent[node] != node) parent[node] = find(parent[node]);
        return parent[node];
    }

    public void union(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) return;

        if (depth[rootX] < depth[rootY]) {
            int temp = rootY;
            rootY = rootX;
            rootX = temp;
        }
        if (depth[rootX] == depth[rootY])
            depth[rootX]++;

        parent[rootY] = rootX;
        this.size[rootX] += this.size[rootY];
    }

    public int count(int node) {
        return this.size[find(node)];
    }

    public int rooftop() {
        return count(size.length - 1) - 1;
    }
}