Bricks Falling When Hit

Identifying Problem Isomorphism

“Bricks Falling When Hit” can be mapped to “Surrounded Regions”.

In “Bricks Falling When Hit”, you are given a 2D grid representing a wall, where each cell is either a brick (1) or not a brick (0). After each hit, if any brick not directly connected to the top of the wall will fall, you need to return an array representing the number of bricks that will fall after each hit.

In “Surrounded Regions”, you are given a 2D board filled with ‘X’ and ‘O’. You need to capture all regions surrounded by ‘X’. A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

The connection lies in the fact that in both problems, you’re dealing with a structure connected to the edges of a 2D grid. Both problems require you to evaluate the grid after an action is taken: removing a brick in “Bricks Falling When Hit” and flipping ‘O’s in “Surrounded Regions”.

“Bricks Falling When Hit” is more complex due to the dynamic nature of the actions, the need to consider gravity, and the multiple hits happening in sequence.

The “Bricks Falling When Hit” problem involves Union Find, Grids, and Backtracking. Here are some problems to build up to this one:

  1. “Number of Islands” (LeetCode 200): This is a foundational problem for understanding grid traversals and connected components, which are both essential concepts for this problem.

  2. “Surrounded Regions” (LeetCode 130): This problem also involves grid traversal and the idea of checking connected components.

  3. “Redundant Connection” (LeetCode 684): This problem introduces the concept of Union-Find which is a key algorithmic tool for this problem.

  4. “Number of Operations to Make Network Connected” (LeetCode 1319): Another problem that deals with Union-Find.

  5. “Max Area of Island” (LeetCode 695): This problem helps with understanding how to calculate connected areas in a grid.

  6. “Friend Circles” (LeetCode 547): This problem is a good introduction to Union-Find in the context of relationships.

  7. “Most Stones Removed with Same Row or Column” (LeetCode 947): Another grid-based Union-Find problem.

  8. “Graph Valid Tree” (LeetCode 261): This problem can help further your understanding of how to use Union-Find to solve graph problems.

  9. “Swim in Rising Water” (LeetCode 778): This problem involves grid traversal and pathfinding, which are useful skills for this problem.

  10. “Path With Maximum Minimum Value” (LeetCode 1102): This is a more advanced grid traversal problem that can help build your skills for this problem.

You will get familiar with the concepts of Union Find, Grids, and Backtracking that you will need to understand to solve the “Bricks Falling When Hit” problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
        def dfs(i, j):
            if not (0 <= i < R and 0 <= j < C) or grid[i][j] != 1:
                return 0
            res = 1
            grid[i][j] = 2
            for x, y in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                res += dfs(i+x, j+y)
            return res

        def is_connected(i, j):
            return i == 0 or any([0 <= i+x < R and 0 <= j+y < C 
              and grid[i+x][j+y] == 2 for x, y in [(0, 1), (1, 0), (0, -1), (-1, 0)]])

        R, C = len(grid), len(grid[0])
        for i, j in hits:
            grid[i][j] -= 1

        for i in range(C):
            dfs(0, i)

        res = [0]*len(hits)
        for k in range(len(hits)-1, -1, -1):
            i, j = hits[k]
            grid[i][j] += 1
            if grid[i][j] == 1 and is_connected(i, j):
                res[k] = dfs(i, j) - 1
        return res

Problem Classification

This problem falls under the category of Dynamic Programming, Graphs, and Simulation.

‘What’ components

  • We have a binary grid representing a 2D array, with 1s representing bricks and 0s representing empty spaces.
  • We are given an array hits that represents the sequence of bricks to be removed from the grid. The removal of a brick may cause other bricks to become unstable and fall.
  • The rules of stability for a brick are clearly defined in the problem: it’s either directly connected to the top of the grid or it’s adjacent to at least one stable brick.
  • The task is to calculate how many bricks fall after each erasure in the sequence.

Based on the components, we can further classify the problem:

  1. Data Structures: We are working with a 2D grid (which can be interpreted as a 2D array or matrix) and an array of hits (coordinates of bricks to remove).

  2. Graphs: The connections between bricks can be thought of as a graph. A brick is stable if it’s connected to the top or to a stable brick.

  3. Simulation: The problem involves simulating a sequence of actions (brick removals) and tracking the changes in state (falling bricks) that each action causes.

  4. Dynamic Programming: There’s a need to keep track of states (stable/unstable bricks) after each hit, which suggests that solutions to subproblems could potentially be reused.

  5. Combinatorics: The falling of bricks depends on the combination of bricks and their state (stable/unstable) around a given brick.

The categorizations indicate that the problem requires a blend of techniques from dynamic programming, graph theory, and simulation to be solved effectively.

Clarification Questions

What are the clarification questions we can ask about this problem?

Identifying Problem Isomorphism

Constraints

Given the constraints and problem statement, we can identify the following characteristics:

Grid Size:

The grid size is at most 200 x 200, which means the total number of cells is at most 40,000. This is relatively moderate and allows us to apply algorithms with a time complexity up to O(n^2) or O(n^3).

Binary Grid:

The grid contains only binary values (1s and 0s). This simplifies some calculations and operations because we only need to consider two states.

Brick Stability:

A brick’s stability depends only on its immediate neighbours and its vertical position in the grid. This local dependency can be exploited to efficiently calculate whether a brick is stable or not.

Erasures:

The maximum number of erasures is 4 * 10^4. As each erasure can affect the stability of neighbouring bricks, tracking these changes for each erasure operation is a key part of the solution.

All Erasure Positions Are Unique:

This eliminates the need to handle cases where the same brick would be removed multiple times.

Stability Depends on Connection to Top:

This suggests we can use techniques like Depth-First Search or Union-Find to determine the connected components and identify which bricks are stable.

Order of Erasures Matters:

The sequence in which bricks are removed can affect the number of bricks that fall. This means we need to process the erasures in the order they’re given.

By considering these characteristics and constraints, we can guide our approach to an efficient solution. They allow us to eliminate some potential solutions that wouldn’t work under these conditions and concentrate on those that leverage these characteristics.

Thought Process

Can we assume that all initial bricks are stable?

No, we can’t assume that all initial bricks are stable. A brick is considered 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. Therefore, a brick that is not connected to the top of the grid and doesn’t have any adjacent stable bricks is considered unstable and will fall.

In the context of the problem, before any erasures are applied, a brick can be assumed to be stable if it is directly connected to the top of the grid or is connected to a brick that is itself stable. The stability of bricks can change as erasures are applied and bricks are removed from the grid. If a brick loses its connection to the top of the grid and all of its stable neighbors, it becomes unstable and will fall. So the initial stability of the bricks is dependent on their position and the configuration of the grid.

Why in solution we need to reversely add bricks back?

This approach is adopted because we are simulating the process of erasing the bricks in the grid. When a brick is erased from the grid, it might cause some other bricks to fall as they could lose their stability. In other words, the effect of erasing a brick is not isolated; it can influence the stability of the surrounding bricks. This effect also depends on the order in which bricks are erased.

For instance, erasing a brick at the beginning might cause a brick to fall, which, if it had been present, could have stabilized another brick later in the sequence of erasures. But if we reverse the process, adding back the bricks in the reverse order of erasure, we are effectively checking for each brick whether its erasure caused other bricks to fall.

By reversing the sequence, we can incrementally check how many bricks would fall (if any) for each brick re-added. This is because adding a brick might provide stability to other bricks, and hence prevent them from falling in the subsequent operations, which we are now simulating in reverse.

This approach helps to accurately calculate the number of bricks that will fall after each erasure.

This sounds like Mikado method to refactor a codebase.

Yes, you’re correct! The “Mikado Method” is a structured way to perform major refactoring of code where you create a graph of dependencies to visualize and handle all the necessary changes. The name comes from the pick-up sticks game Mikado where you have to remove a stick without disturbing the others.

The method described for solving this problem follows a similar principle. In the given problem, when we remove a brick, it may cause other bricks to fall (disturbances in the system). In the Mikado Method, we would create a graph showing the dependencies between the sticks, allowing us to remove them without causing a disturbance.

Reversing the operations (adding bricks back in reverse order) can be seen as a way to refactor the “codebase” of the grid in a manner that we ensure the stability (in this case, literal physical stability) of the entire system after each change.

It’s an interesting analogy and a good way to understand the problem-solving strategy here!

Case Analysis

If no bircks drop, then after all operations. The grid will be look like a pool with multi islands. For example:

0010000100
0111001110
1111111111

After operations: [0,2], [2,4], [1,2], [0,7]

0000000000
0101001110
1111011111

so total 2 islands.

Then add bricks back reversely.

[0,7]
0000000100
0101001110
1111011111

The right island attaches top, and its size is 9, which means 8 bricks drop in this operation.

[1,2]
0000000100
0111001110
1111011111

The left island does not reach the top, so no brick drops.

[2,4]
0000000100
0111001110
1111111111

The left island connects to right island and acttaches top, and left island is original 7, which means 7 bricks drop in this operation.

[0,2]
0010000100
0111001110
1111111111

The island size is just enlarged by 1, which means no brick drops.

In this interpretation, we can think of the grid as a pool containing multiple islands, where each island is a group of connected bricks. When we hit a brick, it’s like we’re removing part of the land. If this removal causes an island to be no longer connected to the top of the grid (the “sky”), that island is no longer stable and all of its bricks “fall”, or are removed.

Let’s break down the explanation step by step:

Initial state

The grid starts off with two islands. One spans the columns 1 through 3 and the other one spans the columns 5 through 8. Both of these islands are connected to the top of the grid.

After operation [0,2], [2,4], [1,2], [0,7]:

The bricks at these coordinates are removed, breaking the islands up. This results in the bricks that are no longer connected to the top falling away. The grid now looks like a pool with two separate islands.

Add bricks back in reverse order:

  1. Operation [0,7]: Adding back this brick causes the right island to reconnect to the top. This means that all the bricks that had fallen off when we originally removed this brick (8 bricks) now drop back onto the grid.

  2. Operation [1,2]: Adding back this brick doesn’t connect any island to the top. So, no bricks drop.

  3. Operation [2,4]: Adding back this brick causes the left island to reconnect to the top. So, all the bricks that had fallen off when we originally removed this brick (7 bricks) now drop back onto the grid.

  4. Operation [0,2]: Adding back this brick only enlarges the size of the existing island. It doesn’t connect any new islands to the top, so no bricks drop.

This is a visual way to understand the process of hitting and dropping bricks. It also highlights the importance of the order of operations. When adding the bricks back in reverse order, we are effectively simulating the state of the grid before each hit, which allows us to accurately calculate the number of bricks that will fall after each hit.

The problem involves the concept of graph theory and depth-first search (DFS). To solve this problem, we must simulate the process backward.

Reverse Process:

A key insight from the problem statement is to process the hits in reverse order. This way, we can avoid dealing with the dynamic changes of brick stability after each hit.

Stability Assessment:

Next, we need to determine whether each brick is stable or not. This can be done by performing a DFS from the top row (as they are always stable) and marking each visited brick as stable.

Brick Removal and Count:

After knowing the stable bricks, we can remove the hit bricks one by one from the last. For each hit, we count the number of unstable bricks that were connected to it, make it stable, and add the count to the result.

Helper Functions:

We would need helper functions to perform the DFS (to check stability) and to get the neighbors of a cell.

Given these steps, we can now write our Python code.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

def hitBricks(grid, hits):
    def dfs(i, j):
        if not (0 <= i < R and 0 <= j < C) or grid[i][j] != 1:
            return 0
        res = 1
        grid[i][j] = 2
        for x, y in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            res += dfs(i+x, j+y)
        return res

    def is_connected(i, j):
        return i == 0 or any([0 <= i+x < R and 0 <= j+y < C 
          and grid[i+x][j+y] == 2 for x, y in [(0, 1), (1, 0), (0, -1), (-1, 0)]])

    R, C = len(grid), len(grid[0])
    for i, j in hits:
        grid[i][j] -= 1

    for i in range(C):
        dfs(0, i)

    res = [0]*len(hits)
    for k in range(len(hits)-1, -1, -1):
        i, j = hits[k]
        grid[i][j] += 1
        if grid[i][j] == 1 and is_connected(i, j):
            res[k] = dfs(i, j) - 1
    return res

The function dfs is used to do a depth-first search from the top row to find and mark all stable bricks. The function is_connected is used to check if a brick is connected to the top row or to a stable brick. It does this by checking all four directions from the current brick.

In the main function hitBricks, we first mark all hit bricks, then perform the DFS from the top row to find all stable bricks. After that, we go through the hits list in reverse order, and for each hit, we add the number of bricks that will fall to the result list.

This Python code takes into account all the insights we derived from the problem statement and uses them to arrive at an efficient solution.

Language Agnostic Coding Drills

Dissect the code and identify each distinct concept it contains.

The concepts used in this code are:

  • Nested Functions: The dfs and is_connected functions are defined within the main function. This allows the code to be organized and more readable.

  • Depth-First Search (DFS): This is a common algorithm for traversing or searching tree or graph data structures. It is implemented in the dfs function here, and is used to calculate the size of the connected components in the grid.

  • Grid Traversal: This is a fundamental concept in problems involving 2D matrices or grids. It is used in multiple places in the code.

  • Use of Directories for Traversal: The for x, y in [(0, 1), (1, 0), (0, -1), (-1, 0)]: pattern represents the four cardinal directions (right, down, left, and up). It is used to navigate the grid in all four directions from a particular cell.

  • List Comprehension: This is a concise way to create lists based on existing lists (or other iterable objects). Here, it is used to check if a cell is connected to the top of the grid or another stable brick.

Order the identified concepts or drills in order of increasing difficulty.

  • Nested Functions: Beginner. They are a basic concept in Python and help with code organization.

  • List Comprehension: Beginner to Intermediate. While they are a fundamental concept in Python, understanding and writing complex list comprehensions can be challenging for beginners.

  • Use of Directories for Traversal: Intermediate. It requires understanding how 2D grid traversal works and how to represent the cardinal directions as pairs of coordinates.

  • Grid Traversal: Intermediate. It is a standard algorithm for navigating 2D arrays or matrices, and is used frequently in programming problems.

  • Depth-First Search (DFS): Intermediate to Advanced. It is an essential algorithm for graph traversal, but can be complex to understand and implement correctly, especially for beginners.

Describe the problem-solving approach from the problem statement to the final solution.

The code first reduces the number of bricks at each hit location, then uses DFS from the top row to find all stable bricks. Next, it reverses the hit operations, and for each brick that is put back and is connected to the top row or another stable brick, it runs DFS again to calculate the number of bricks that will fall (the size of the connected component minus one). This is a clever application of DFS and grid traversal, showing how these fundamental concepts can be combined to solve a complex problem.

Targeted Drills in Python

Grid traversal and cell access:

Create a 2D grid (list of lists) in Python and practice accessing and modifying specific cells. You can start with simple operations like filling the grid with a specific number, changing the values of cells, etc. This forms the basis of manipulating 2D arrays or grids, which is essential in this problem.

1
2

grid = [[0 for _ in range(5)] for _ in range(5)]
grid[2][2] = 1  # Change the value of a specific cell

DFS (Depth-First Search):

Write a recursive function to perform DFS on a 2D grid. Practice identifying the base case and the recursive case.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def dfs(grid, x, y):
    if x < 0 or y < 0 or x >= len(grid) 
             or y >= len(grid[0]) 
             or grid[x][y] != 1:
        return
    grid[x][y] = 2  # Marking the cell as visited
    dfs(grid, x + 1, y)
    dfs(grid, x - 1, y)
    dfs(grid, x, y + 1)
    dfs(grid, x, y - 1)

Working with List of Lists:

Write functions to manipulate a list of lists (which is essentially what a 2D grid is). You can practice creating, appending to, and removing from a list of lists, which are all operations we use in this problem.

1
2

list_of_lists = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
flattened_list = [item for sublist in list_of_lists for item in sublist]  # Flatten a list of lists

Problem-specific Concept (Checking the Stability of Bricks):

Create a function that takes a grid and a brick’s position, and checks if the brick is connected to the top of the grid or to any other stable brick.

1
2
3
4
5
6
7

def is_stable(grid, x, y):
    if x == 0 or any([0 <= nx < len(grid) 
      and 0 <= ny < len(grid[0]) 
      and grid[nx][ny] == 2 
          for nx, ny in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]]):
        return True
    return False

Once you’re comfortable with these individual drills, you can start integrating them. Begin by initializing the grid and applying the ‘hits’. Then, perform a DFS from the top row to identify and mark all stable bricks. After this, iterate through the ‘hits’ in reverse order, adding each brick back and checking if it’s stable and connected to any other stable brick (using DFS). If it is, run DFS to identify any new stable bricks and add them to the count of bricks that didn’t fall. This should give you the solution to the problem.