Solution:

This is a trick problem. I will come later to explain why. So the most logical approach to solve the problem is to first 'hit & erase' one of the brick A and then for each of the adjacent bricks of A, check if they are 'connected' to the top of the grid. If they are connected to the top of the grid don't do anything, else for all bricks that are connected to the adjacent bricks of A, 'drop' them. Do this for all hits. To find whether an adjacent brick of A is connected to the top of grid or not, do a DFS. Here is simple python code to do this:

import collections class Solution(object): def is_connected(self, grid, x, y, n, m): stack, result = [(x,y)], [] visited = set([(x, y)]) while len(stack) > 0: u, v = stack.pop() result.append((u,v)) if u == 0: return True, result for i in [-1,1]: if 0 <= u+i < n and 0 <= v < m and grid[u+i][v] == 1 and (u+i, v) not in visited: stack.append((u+i,v)) visited.add((u+i,v)) if 0 <= u < n and 0 <= v+i < m and grid[u][v+i] == 1 and (u, v+i) not in visited: stack.append((u,v+i)) visited.add((u,v+i)) return False, result def drop_bricks(self, grid, x, y, n, m): dropped = 0 if 0 < x < n and 0 <= y < m and grid[x][y] == 1: connected, result = self.get_connected(grid, x, y, n, m) if connected is False: dropped = len(result) for x, y in result: grid[x][y] = 0 return dropped def hitBricks(self, grid, hits): n, m = len(grid), len(grid[0]) out = [] for x, y in hits: if grid[x][y] == 1: grid[x][y] = 0 a1 = self.drop_bricks(grid, x+1, y, n, m) a2 = self.drop_bricks(grid, x-1, y, n, m) a3 = self.drop_bricks(grid, x, y+1, n, m) a4 = self.drop_bricks(grid, x, y-1, n, m) out.append(a1+a2+a3+a4) else: out.append(0) return out

If a brick B is not connected to the top of the grid, then there is no problem as we have already found all the bricks connected to B and it is just a matter of setting the value of all these cells to 0 and tracking the number of bricks fallen with this hit. Note that once a brick is fallen we never visit that cell in future, thus for all fallen bricks we never repeat that cell position while traversing.

The problem arises if the brick B is connected to the top of the grid. In this case, although we might have detected all bricks connected to B, but we cannot set their cell values to 0 and thus the DFS search goes in vain. Note that we cannot memoize the fact that a brick is connected to the top because the brick may not remain connected in future hits and drops. Thus we need to traverse a brick multiple times till it is either 'hit' or 'fallen' due to a hit.

Running time analysis : If at-least one brick 'falls' with each 'hit' then the run-time complexity is O(N*M) where N is the number of rows and M is the number of columns, because the maximum number of bricks that can fall is N*M and since each fallen brick is visited only once, the run time complexity is O(N*M). Note that it does not depend on the number of hits because we are assuming that at-least one brick falls with each 'hit'.

But if among K hits, only for P hits at-least one brick falls, then for the remaining K-P hits, we need to do a DFS on the entire grid possibly. Each DFS has a worst case run-time complexity of O(NM). Thus total run-time complexity is O((K-P)*N*M + N*M). Also the number of hits could be at max O(N*M) and if none of the hits actually 'drops' a brick then in that worst case the run-time complexity is O((NM)^{2}).

Now here comes the trick part. Instead of counting the number of bricks fallen with each hit, we will first do all the hits together, then 'drop' all the bricks that could possible drop for all the hits, and then restore back the drops in the reverse order of the hits and count how many drops are restored for each reverse hit. This ensures that while restoring we only limit ourselves to the bricks that has been fallen. Also we can safely use memoization for a brick which is connected because a brick once found to be connected to the top will always remain connected for each reverse hit because we are restoring bricks instead of dropping bricks.

Here is the Python code for the trick approach:

import collections class Solution(object): def get_connected(self, grid, x, y, n, m, is_connected, early_return=False): stack, result = [(x,y)], [] visited = set([(x, y)]) while len(stack) > 0: u, v = stack.pop() result.append((u,v)) if u == 0 or ((u,v) in is_connected and is_connected[(u,v)] == 1): return True, result if early_return and (u,v) in is_connected and is_connected[(u,v)] == -1: return False, result for i in [-1,1]: if 0 <= u+i < n and 0 <= v < m and grid[u+i][v] == 1 and (u+i, v) not in visited: stack.append((u+i,v)) visited.add((u+i,v)) if 0 <= u < n and 0 <= v+i < m and grid[u][v+i] == 1 and (u, v+i) not in visited: stack.append((u,v+i)) visited.add((u,v+i)) return False, result def get_deleted_neighbors(self, grid, x, y, n, m, is_connected): stack, result = [(x,y)], [] visited = set([(x, y)]) while len(stack) > 0: u, v = stack.pop() result.append((u,v)) for i in [-1,1]: if 0 <= u+i < n and 0 <= v < m and grid[u+i][v] == 2 and (u+i, v) not in visited: stack.append((u+i,v)) visited.add((u+i,v)) if 0 <= u < n and 0 <= v+i < m and grid[u][v+i] == 2 and (u, v+i) not in visited: stack.append((u,v+i)) visited.add((u,v+i)) return result def drop_bricks(self, grid, x, y, n, m, is_connected): if 0 <= x < n and 0 <= y < m and grid[x][y] == 1: connected, result = self.get_connected(grid, x, y, n, m, is_connected) for x, y in result: if connected is False: grid[x][y] = 2 is_connected[(x,y)] = 1 if connected else -1 def hitBricks(self, grid, hits): n, m = len(grid), len(grid[0]) is_connected = dict() for x in range(len(grid)): for y in range(len(grid[0])): if grid[x][y] == 1: is_connected[(x,y)] = 0 for x, y in hits: if grid[x][y] == 1: grid[x][y] = -1 for x, y in hits: if grid[x][y] == -1: self.drop_bricks(grid, x+1, y, n, m, is_connected) self.drop_bricks(grid, x-1, y, n, m, is_connected) self.drop_bricks(grid, x, y+1, n, m, is_connected) self.drop_bricks(grid, x, y-1, n, m, is_connected) out, disconnected_hits = [0]*len(hits), [] for i in reversed(range(len(hits))): x, y = hits[i] if grid[x][y] == -1: grid[x][y] = 2 connected, _ = self.get_connected(grid, x, y, n, m, is_connected, early_return=True) is_connected[(x,y)] = 1 if connected else -1 if connected: deleted_neighbors = self.get_deleted_neighbors(grid, x, y, n, m, is_connected) grid[x][y] = 1 cnts = len(deleted_neighbors)-1 for u, v in deleted_neighbors: grid[u][v] = 1 is_connected[(u,v)] = 1 out[i] = cnts else: disconnected_hits.append(i) for i in disconnected_hits: x, y = hits[i] if is_connected[(x,y)] == -1: grid[x][y] = 1 deleted_neighbors = self.get_deleted_neighbors(grid, x, y, n, m, is_connected) cnts = len(deleted_neighbors)-1 out[i] = cnts return out

In this approach, we keep a memoization dictionary 'is_connected', which is initialized to 0 for each cell with a 1. First we 'remove' all bricks at the positions of the hits by setting grid[x][y]=-1 if grid[x][y] == 1. Then by repeated calling of the 'drop_bricks' method, we drop all bricks that could possible drop. This step is O(N*M) because we do not cover a cell more than once. If a cell is connected to the top, then we return immediately else we drop it and never see it again.

Instead of setting the value of cell to 0 for each dropped brick, we set the value of the cell to 2, so that we can track later that this brick was dropped.

Next step is to restore the dropped bricks. The idea here is that if some bricks got dropped due to a hit it means that due to that hit, the dropped bricks actually got disconnected from the top. Thus if we restore that hit and it is now connected to the top, then all dropped bricks i.e. cell values of 2 that are directly reachable, are the bricks that got dropped. We restore them by resetting the cell values to 1. But it may also happen that the brick that was hit, was already disconnected and anyway all bricks connected to it would have dropped.

Either we can consider this as a valid use case or we can consider them as 'floating' bricks and ignore them. Anyway none of the test cases had this 'floating' bricks scenario. We track such hits in the array 'disconnected_hits' and we separately process them. Observe that if during reverse hits, we encounter 'floating' bricks scenario and if for some earlier hit, these 'floating' bricks were already dropped then their counts will be nullified so it does not matter whether we consider 'floating' bricks.

The run-time complexity of this approach is O(N*M). The codes are also shared on my Github page.

Categories: PROBLEM SOLVING

Tags: Bricks Falling, Depth First Search, DFS, Graph Theory, Trick Problem

### Leave a Reply

You must be logged in to post a comment.