How do you solve Bricks Falling When Hit on LeetCode?

Bricks Falling When Hit (LeetCode #803) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(α(n)) per operation, O(h) overall time complexity and O(n) space complexity. Key insight: Understanding stability is crucial; a brick is stable if connected to the top or adjacent to another stable brick.

What is the brute force solution for Bricks Falling When Hit?

The brute force approach for Bricks Falling When Hit is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves simulating each hit and checking the stability of the bricks after each hit. This is straightforward but inefficient, as we repeatedly check the entire grid for stability. The optimal Optimal Solution approach improves this to O(α(n)) per operation, O(h) overall.

What algorithm or data structure is used to solve Bricks Falling When Hit?

Bricks Falling When Hit uses the following concepts: Array, Union-Find, Matrix. The recommended patterns to study are: Union-Find, Dynamic Connectivity, Graph Traversal.

What are the interview tips for Bricks Falling When Hit?

Explain your thought process clearly; interviewers value understanding over just getting the right answer. Consider edge cases and discuss them with the interviewer to demonstrate thoroughness. Practice implementing Union-Find as it's a common pattern in connectivity problems.

What are common mistakes when solving Bricks Falling When Hit?

Not properly handling edge cases where hits do not affect any bricks. Failing to reset the grid state after processing hits, leading to incorrect results.

#803

Bricks Falling When Hit

Hard

ArrayUnion-FindMatrixUnion-FindDynamic ConnectivityGraph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(α(n)) per operation, O(h) overall
Space	O(1)	O(n)

💡

Intuition

Time O(α(n)) per operation, O(h) overallSpace O(n)

The optimal solution uses a Union-Find (Disjoint Set Union) data structure to efficiently manage the stability of bricks and their connections. This allows us to quickly determine which bricks are stable after each hit and how many fall.

⚙️

Algorithm

4 steps

1Step 1: Initialize a Union-Find structure to manage the connections between bricks.
2Step 2: Mark all bricks as stable that are connected to the top row before processing hits.
3Step 3: Process each hit in reverse order, restoring bricks and checking for stability using the Union-Find structure.
4Step 4: Count how many bricks fall after each restoration.

solution.py55 lines

1# Full working Python code
2class UnionFind:
3    def __init__(self, n):
4        self.parent = list(range(n))
5        self.rank = [1] * n
6
7    def find(self, x):
8        if self.parent[x] != x:
9            self.parent[x] = self.find(self.parent[x])
10        return self.parent[x]
11
12    def union(self, x, y):
13        rootX = self.find(x)
14        rootY = self.find(y)
15        if rootX != rootY:
16            if self.rank[rootX] > self.rank[rootY]:
17                self.parent[rootY] = rootX
18            elif self.rank[rootX] < self.rank[rootY]:
19                self.parent[rootX] = rootY
20            else:
21                self.parent[rootY] = rootX
22                self.rank[rootX] += 1
23
24class Solution:
25    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
26        m, n = len(grid), len(grid[0])
27        uf = UnionFind(m * n + 1)
28        result = [0] * len(hits)
29        # Mark hits
30        for r, c in hits:
31            if grid[r][c] == 1:
32                grid[r][c] = 0
33        # Connect stable bricks
34        for r in range(m):
35            for c in range(n):
36                if grid[r][c] == 1:
37                    if r == 0:
38                        uf.union(c, m * n)
39                    if r > 0 and grid[r-1][c] == 1:
40                        uf.union(r * n + c, (r-1) * n + c)
41                    if c > 0 and grid[r][c-1] == 1:
42                        uf.union(r * n + c, r * n + (c-1))
43        # Process hits in reverse
44        for i in range(len(hits) - 1, -1, -1):
45            r, c = hits[i]
46            if grid[r][c] == 0:
47                grid[r][c] = 1
48                if r == 0:
49                    uf.union(c, m * n)
50                for dr, dc in [(0,1), (1,0), (0,-1), (-1,0)]:
51                    nr, nc = r + dr, c + dc
52                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
53                        uf.union(r * n + c, nr * n + nc)
54                result[i] = max(0, uf.find(c) - 1)
55        return result

ℹ

Complexity note: The time complexity is nearly constant due to the inverse Ackermann function, which is very efficient for the union-find operations. The space complexity is O(n) for the union-find structure.

1Understanding stability is crucial; a brick is stable if connected to the top or adjacent to another stable brick.
2Union-Find is powerful for dynamic connectivity problems, allowing efficient merging and finding of connected components.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.