803. Bricks Falling When Hit #

Problem #

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.

Problem Summary #

We have a grid containing 1s and 0s; 1 represents a brick. A brick will not fall if and only if it is directly connected to the top of the grid, or at least one of its adjacent bricks (in one of the 4 directions) will not fall. We will remove some bricks in sequence. Whenever we remove the position (i, j), the brick at the corresponding position (if it exists) disappears, and then other bricks may fall because of this removal. Return an array representing the number of bricks that fall after each removal operation.

Note:

The number of rows and columns in the grid is in the range [1, 200].
The number of removals will not exceed the area of the grid.
It is guaranteed that each removal is different and is located inside the grid.
A removal position may have no brick; if so, no bricks will fall.

Solution Approach #

Some bricks are connected to the ceiling. The question is: if a certain brick is knocked out, how many bricks will fall? Each brick that is knocked out is not included in the count.
This problem can be solved with Union-Find and DFS. However, students who try DFS will know that the time limit for this problem is very tight. Although DFS can AC, it takes a very long time. If using Union-Find, rank compression must also be performed; otherwise it will also take a very long time. In addition, if Union-Find is used and the total number of each set is counted separately rather than along with the union() operation, it will also lead to timeout. The author got LTE many times here, and finally had to rewrite the UnionFind class, combining the counting operation with the union() operation. Only then did this problem get faster than 100.00% AC.
After getting the problem, first try the brute-force solution: knock out bricks in order, and rebuild the Union-Find after each brick is knocked out. The problem asks how many bricks fall each time; in fact, it is enough to compare how much the number of bricks connected to the ceiling changes each time. Then the solution emerges: first union() all bricks connected to the ceiling, record the number of bricks in this set as count, and then after knocking out a brick each time, rebuild the Union-Find and calculate the number of bricks connected to the ceiling as newCount. newCount - count -1 is the final answer (the knocked-out brick is not counted). After submitting the code, it TLEs.
After TLE occurs, the general idea is usually correct, but the time complexity is too high and needs optimization. Obviously, the part that needs optimization is rebuilding a new Union-Find every time. Is there a way to change from the previous state without rebuilding the Union-Find? If we knock out bricks in the forward direction, then each time we still need to perform DFS starting from this brick, and the time complexity is still very high. What if we think in reverse? First knock out all the bricks that need to be knocked out, and build the Union-Find of the remaining bricks connected to the ceiling after knocking out these bricks. Then add the knocked-out bricks back in reverse order. Each time a brick is added, only refresh its 4 surrounding bricks; DFS is not needed, so the time complexity is greatly optimized. Finally, calculate the final answer according to newCount - count -1. Note that each time a brick is restored, it needs to be colored back to the original brick color 1. With this optimization, it basically will not TLE. If count is calculated separately, it will still TLE. If rank compression is not performed, the time will exceed 1500 ms, so for this problem, if you want to get 100%, every optimization step must be done well. The final 100% answer is shown in the code.

Code #


package leetcode

import (
	"github.com/halfrost/leetcode-go/template"
)

func hitBricks(grid [][]int, hits [][]int) []int {
	if len(hits) == 0 {
		return []int{}
	}
	uf, m, n, res, oriCount := template.UnionFindCount{}, len(grid), len(grid[0]), make([]int, len(hits)), 0
	uf.Init(m*n + 1)
	// First mark the bricks to be hit
	for _, hit := range hits {
		if grid[hit[0]][hit[1]] == 1 {
			grid[hit[0]][hit[1]] = 2
		}
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				getUnionFindFromGrid(grid, i, j, uf)
			}
		}
	}
	oriCount = uf.Count()[uf.Find(m*n)]
	for i := len(hits) - 1; i >= 0; i-- {
		if grid[hits[i][0]][hits[i][1]] == 2 {
			grid[hits[i][0]][hits[i][1]] = 1
			getUnionFindFromGrid(grid, hits[i][0], hits[i][1], uf)
		}
		nowCount := uf.Count()[uf.Find(m*n)]
		if nowCount-oriCount > 0 {
			res[i] = nowCount - oriCount - 1
		} else {
			res[i] = 0
		}
		oriCount = nowCount
	}
	return res
}

func isInGrid(grid [][]int, x, y int) bool {
	return x >= 0 && x < len(grid) && y >= 0 && y < len(grid[0])
}

func getUnionFindFromGrid(grid [][]int, x, y int, uf template.UnionFindCount) {
	m, n := len(grid), len(grid[0])
	if x == 0 {
		uf.Union(m*n, x*n+y)
	}
	for i := 0; i < 4; i++ {
		nx := x + dir[i][0]
		ny := y + dir[i][1]
		if isInGrid(grid, nx, ny) && grid[nx][ny] == 1 {
			uf.Union(nx*n+ny, x*n+y)
		}
	}
}