How hard is LeetCode 803. Bricks Falling When Hit?

LeetCode 803. Bricks Falling When Hit is rated Hard on LeetCode.

What is the time complexity of LeetCode 803. Bricks Falling When Hit?

The Python solution on this page runs in Near O(n) (amortized).

What is the space complexity of LeetCode 803. Bricks Falling When Hit?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 803. Bricks Falling When Hit cover?

LeetCode 803. Bricks Falling When Hit is tagged Union Find, Array and Matrix on LeetCode.

Bricks Falling When Hit — LeetCode 803 Python Solution

HardUnion FindArrayMatrix

Problem: #803
Pattern: Union-Find
Reading time: 8 min
Source: leetcode.com

The problem

You are given an m x n binary grid, where each 1 represents a brick and 0 represents an empty space. A brick is stable if: It is directly connected to the top of the grid, or At least one other brick in its four adjacent cells is stable.

Example

Input: grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
Output: [2]
Explanation: Starting with the grid:

Python solution

Python

class Solution:
    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        def union(a, b):
            pa, pb = find(a), find(b)
            if pa != pb:
                size[pb] += size[pa]
                p[pa] = pb

        m, n = len(grid), len(grid[0])
        p = list(range(m * n + 1))
        size = [1] * len(p)
        g = deepcopy(grid)
        for i, j in hits:
            g[i][j] = 0
        for j in range(n):
            if g[0][j] == 1:
                union(j, m * n)
        for i in range(1, m):
            for j in range(n):
                if g[i][j] == 0:
                    continue
                if g[i - 1][j] == 1:
                    union(i * n + j, (i - 1) * n + j)
                if j > 0 and g[i][j - 1] == 1:
                    union(i * n + j, i * n + j - 1)
        ans = []
        for i, j in hits[::-1]:
            if grid[i][j] == 0:
                ans.append(0)
                continue
            g[i][j] = 1
            prev = size[find(m * n)]
            if i == 0:
                union(j, m * n)
            for a, b in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and g[x][y] == 1:
                    union(i * n + j, x * n + y)
            curr = size[find(m * n)]
            ans.append(max(0, curr - prev - 1))
        return ans[::-1]

Complexity

Measure	Complexity
Time	Near O(n) (amortized)
Space	O(n) auxiliary

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 803. Bricks Falling When Hit is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Union Find.

The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 803. Bricks Falling When Hit?: LeetCode 803. Bricks Falling When Hit is rated Hard on LeetCode.
What is the time complexity of LeetCode 803. Bricks Falling When Hit?: The Python solution on this page runs in Near O(n) (amortized).
What is the space complexity of LeetCode 803. Bricks Falling When Hit?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 803. Bricks Falling When Hit cover?: LeetCode 803. Bricks Falling When Hit is tagged Union Find, Array and Matrix on LeetCode.