@@ -0,0 +1,2237 @@
+# Time:  O(r * c)%0A# Space: O(r * c)%0A%0Aclass UnionFind:%0A    def __init__(self, n):%0A        self.set = range(n+1)%0A        self.size = %5B1%5D*(n+1)%0A        self.size%5B-1%5D = 0%0A%0A    def find_set(self, x):%0A        if self.set%5Bx%5D != x:%0A            self.set%5Bx%5D = self.find_set(self.set%5Bx%5D)  # path compression.%0A        return self.set%5Bx%5D%0A%0A    def union_set(self, x, y):%0A        x_root, y_root = map(self.find_set, (x, y))%0A        if x_root == y_root:%0A            return False%0A        self.set%5Bmin(x_root, y_root)%5D = max(x_root, y_root)%0A        self.size%5Bmax(x_root, y_root)%5D += self.size%5Bmin(x_root, y_root)%5D%0A        return True%0A%0A    def top(self):%0A        return self.size%5Bself.find_set(len(self.size)-1)%5D%0A    %0A%0Aclass Solution(object):%0A    def hitBricks(self, grid, hits):%0A        %22%22%22%0A        :type grid: List%5BList%5Bint%5D%5D%0A        :type hits: List%5BList%5Bint%5D%5D%0A        :rtype: List%5Bint%5D%0A        %22%22%22%0A        def index(C, r, c):%0A            return r*C+c%0A        %0A        directions = %5B(0, -1), (0, 1), (-1, 0), (1, 0)%5D%0A        R, C = len(grid), len(grid%5B0%5D)%0A%0A        hit_grid = %5Brow%5B:%5D for row in grid%5D%0A        for i, j in hits:%0A            hit_grid%5Bi%5D%5Bj%5D = 0%0A%0A        union_find = UnionFind(R*C)%0A        for r, row in enumerate(hit_grid):%0A            for c, val in enumerate(row):%0A                if not val: continue%0A                if r == 0:%0A                    union_find.union_set(index(C, r, c), R*C)%0A                if r and hit_grid%5Br-1%5D%5Bc%5D:%0A                    union_find.union_set(index(C, r, c), index(C, r-1, c))%0A                if c and hit_grid%5Br%5D%5Bc-1%5D:%0A                    union_find.union_set(index(C, r, c), index(C, r, c-1))%0A%0A        result = %5B%5D%0A        for r, c in reversed(hits):%0A            prev_roof = union_find.top()%0A            if grid%5Br%5D%5Bc%5D == 0:%0A                result.append(0)%0A                continue%0A            for d in directions:%0A                nr, nc = (r+d%5B0%5D, c+d%5B1%5D)%0A                if 0 %3C= nr %3C R and 0 %3C= nc %3C C and hit_grid%5Bnr%5D%5Bnc%5D:%0A                    union_find.union_set(index(C, r, c), index(C, nr, nc))%0A            if r == 0:%0A                union_find.union_set(index(C, r, c), R*C)%0A            hit_grid%5Br%5D%5Bc%5D = 1%0A            result.append(max(0, union_find.top()-prev_roof-1))%0A        return result%5B::-1%5D%0A

Create bricks-falling-when-hit.py