803 Bricks Falling When Hit

803. Bricks Falling When Hit

1. Question

We have a grid of 1s and 0s; the 1s in a cell represent bricks. A brick will not drop if and only if it is directly connected to the top of the grid, or at least one of its (4-way) adjacent bricks will not drop.

We will do some erasures sequentially. Each time we want to do the erasure at the location (i, j), the brick (if it exists) on that location will disappear, and then some other bricks may drop because of that erasure.

Return an array representing the number of bricks that will drop after each erasure in sequence.

Example 1:
Input:

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

Output:
 [2]

Explanation: 

If we erase the brick at (1, 0), the brick at (1, 1) and (1, 2) will drop. So we should return 2.

Example 2:
Input:

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

Output:
 [0,0]

Explanation: 

When we erase the brick at (1, 0), the brick at (1, 1) has already disappeared due to the last move. So each erasure will cause no bricks dropping.  Note that the erased brick (1, 0) will not be counted as a dropped brick.

Note:

• The number of rows and columns in the grid will be in the range [1, 200].

• The number of erasures will not exceed the area of the grid.

• It is guaranteed that each erasure will be different from any other erasure, and located inside the grid.

• An erasure may refer to a location with no brick - if it does, no bricks drop.

2. Implementation

(1) Union Find

思路: 这题题设是当brick通过hits数组打碎后，所有和第一行没有连在一起的brick就会掉落，问有多少brick会掉落。步骤如下:

(1) 我们可以用union find做。但union find只能连接不能断开，所以我们应该先处理hit brick之后的grid，找到所有connected component. 对于与第一行相连的component。我们用m * n这个特殊id表示和top连接的component, 因为按照row * n + col的方式定义union find的node id，m * n这个id是grid所有cell无法转换，非常适合做一个特殊id

(2) 找到hit之后的所有connected components后，我们倒过来把hit之后的brick加回去，每加一次的时候，查看和top连接的component的size，如果比之前的大，则有falling bricks，个数为newSize - size - 1,这里newSize是加上hit之后，与connected component的size，size是之前与top连接的component的size, 这里还要再减1是因为我们不算被hit的brick

class Solution {
    public int[] hitBricks(int[][] grid, int[][] hits) {
        if (grid == null || grid.length == 0) {
            return new int[0];
        }

        int m = grid.length;
        int n = grid[0].length;

        for (int[] hit : hits) {
            if (grid[hit[0]][hit[1]] == 1) {
                grid[hit[0]][hit[1]] = 2;
            }
        }

        UnionFind uf = new UnionFind(m *n + 1);
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        // Get all connected components after the hit
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    connectNeighbors(i, j, uf, directions, grid);
                }
            }
        }

        // Find the original size of the component connected to the top
        int size = uf.size[uf.find(m * n)];
        int[] res = new int[hits.length];
        int newSize = 0; 

        // Reversely adding the hit brick to get size of connected component conencted to the top
        // The number of falling bricks of each hit will be the difference fo the size of the component connected to top
        for (int i = hits.length - 1; i >= 0; i--) {
            int[] hit = hits[i];
            if (grid[hit[0]][hit[1]] == 2) {
                connectNeighbors(hit[0], hit[1], uf, directions, grid);
                grid[hit[0]][hit[1]] = 1;
            }

            newSize = uf.size[uf.find(m * n)];
            if (newSize > size) {
                // we minus one here because the hit brick should not be counted
                res[i] = newSize - size - 1;
            }
            size = newSize;
        }
        return res;
    }

    // Connect brick in 4 directions
    public void connectNeighbors(int row, int col, UnionFind uf, int[][] directions, int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        for (int[] direction : directions) {
            int nextRow = row + direction[0];
            int nextCol = col + direction[1];

            if (isValid(nextRow, nextCol, grid)) {
                uf.union(row * n + col, nextRow * n + nextCol);
            }
        }

        // Use m * n as the special node id for connected component connected to the top row
        if (row == 0) {
            uf.union(row * n + col, m * n);
        }
    }

    public boolean isValid(int row, int col, int[][] grid) {
        return row >= 0 && row < grid.length && col >= 0 && col < grid[0].length && grid[row][col] == 1;
    }

    class UnionFind {
        int[] sets;
        int[] size;

        public UnionFind(int n) {
            sets = new int[n];
            size = new int[n];

            for (int i = 0; i < n; i++) {
                sets[i] = i;
                size[i] = 1;
            }
        }

        public int find(int node) {
            while (node != sets[node]) {
                node = sets[node];
            }
            return node;
        }

        public void union(int i, int j) {
            int node1 = find(i);
            int node2 = find(j);

            if (node1 == node2) {
                return;
            }

            sets[node1] = node2;
            size[node2] += size[node1];
        }
    }
}

3. Time & Space Complexity

Union Find: 时间复杂度O(mn * (k + mn)), k是hits数组的长度，unionfind里的find()最坏情况是O(mn), 在加上被hit的brick的过程中，我们每次都将被hit的brick的与四周union，这个过程要O(mn), 总共有k次，所以这步需要O(mnk). 另一部分时间是在刚开始找出在hit之后所有connected component的过程，这部分需要O(mn^2)。空间复杂度O(mn)