public int[] hitBricks(int[][] grid, int[][] hits) {
if (grid == null || grid.length == 0) {
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++) {
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];
// 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--) {
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)];
// we minus one here because the hit brick should not be counted
res[i] = newSize - size - 1;
// Connect brick in 4 directions
public void connectNeighbors(int row, int col, UnionFind uf, int[][] directions, int[][] grid) {
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
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;
public UnionFind(int n) {
for (int i = 0; i < n; i++) {
public int find(int node) {
while (node != sets[node]) {
public void union(int i, int j) {
size[node2] += size[node1];