Sponsored
Sponsored
This approach involves processing the hits in reverse order and leveraging a union-find data structure to efficiently manage brick connectivity. The idea is to treat the grid by marking each brick in the grid as destroyed first (based on the hits) and then process each hit in reverse order, restoring the brick back in the grid. If restoring a brick causes previously unstable bricks to stabilize (due to reconnection to the top), then count these bricks as 'falling' during the original 'hit' sequence.
Time Complexity: O((m * n) + h * alpha(m * n)), where h is the number of hits, and alpha is the inverse Ackermann function for path compression in union-find. Space Complexity: O(m * n) for the union-find structure.
1class UnionFind:
2 def __init__(self, size):
3 self.parent = list(range(size))
4 self.rank = [1] * size
5 self.size = [1] * size
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 self.size[rootX] += self.size[rootY]
19 elif self.rank[rootX] < self.rank[rootY]:
20 self.parent[rootX] = rootY
21 self.size[rootY] += self.size[rootX]
22 else:
23 self.parent[rootY] = rootX
24 self.rank[rootX] += 1
25 self.size[rootX] += self.size[rootY]
26
27 def top_connected(self, x):
28 return self.find(x) == self.find(0)
29
30 def get_size(self, x):
31 return self.size[self.find(x)]
32
33class Solution:
34 def hitBricks(self, grid, hits):
35 m, n = len(grid), len(grid[0])
36 union_find = UnionFind(m * n + 1)
37 grid_copy = [row[:] for row in grid]
38
39 # Apply all hits
40 for x, y in hits:
41 grid_copy[x][y] = 0
42
43 # Connect stable bricks to union-find starting with the first row
44 for j in range(n):
45 if grid_copy[0][j] == 1:
46 union_find.union(j, m * n)
47
48 directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
49 def index(x, y):
50 return x * n + y
51
52 def union_around(x, y):
53 for dx, dy in directions:
54 nx, ny = x + dx, y + dy
55 if 0 <= nx < m and 0 <= ny < n and grid_copy[nx][ny] == 1:
56 union_find.union(index(x, y), index(nx, ny))
57
58 # After hitting, reinstate bricks and union neighbors if they possibly stabilizes
59 res = []
60 for x, y in reversed(hits):
61 if grid[x][y] == 1:
62 grid_copy[x][y] = 1
63
64 prev_top_size = union_find.get_size(m * n)
65 if x == 0:
66 union_find.union(index(x, y), m * n) # Connect this restored to top
67 union_around(x, y)
68 new_top_size = union_find.get_size(m * n)
69 res.append(max(0, new_top_size - prev_top_size - 1))
70 else:
71 res.append(0)
72
73 return res[::-1]This Python solution constructs a union-find data structure to manage connectivity among bricks. Grid cells are treated as nodes, with an additional node representing the 'top row'. The union-find structure allows for dynamic connectivity management as bricks are restored in reverse of the original hits. When a brick is restored, we check which bricks it makes stable (union to the top), counting the difference in connected components size to determine the number of stabilized bricks.
This alternative approach involves using Breadth-First Search (BFS) to identify and maintain stability information within the grid. After simulating the hits by removing the corresponding bricks from the grid, iterate through each cell that remains, performing BFS to determine which bricks are stable by connecting them to the top row directly or indirectly. Calculate how many become unstable after each hit in reverse.
Time Complexity: O((m * n) * (h + 1)), for grid exploration per hit in worst BFS case. Space Complexity: O(m * n) for visited grid and auxiliary data.
1from collections import deque
2
3def stable_grid(grid):
4
The Union-Find algorithm, also known as Disjoint Set Union (DSU), is used to manage a collection of disjoint (non-overlapping) sets. In this approach, we treat each brick as a node in a graph, and two bricks are connected if they are adjacent.
The key insight here is that the process of removing a brick and causing others to fall can be reversed by processing the hits in reverse order. Essentially, we 'add' bricks instead and track when they become stable using the Union-Find structure.
By processing in reverse, every time a brick is re-added, we can check its impact on other previously disconnected bricks and accurately determine how many fall (or in this reverse logic, how many become stable).
Time Complexity: O((m * n) + h), where m is the number of rows, n is the number of columns, and h is the number of hits, as each operation finds or unions amortized over time.
Space Complexity: O(m * n), mainly due to the Union-Find structure.
1
This Python solution employs BFS to identify which bricks remain stable, starting from restoration of each hit. It computes which bricks remain unvisited (unstable) after reintroducing each brick in 'hits' order. Stones connected to the top, directly or indirectly, are stable. After each restoration, it checks all potential connections, only considering valid and new stable bricks.
This solution employs a Union-Find data structure to manage sets of connected bricks and a reverse approach for hit processing. Initially, bricks are marked and connections established to represent already stable bricks.
By iterating reversely over the hits, each 'removed' brick (in original operation) is revisited, and its stabilization impact is calculated by observing changes in the count of bricks connected to the top.