803. Bricks Falling When Hit

HardUnion FindArrayMatrix
Leetcode Link

Problem Description

In this problem, we are given a 2D grid representing a wall of bricks where each cell can either contain a brick (1) or be empty (0). A brick is stable if it's either at the top of the grid or connected to at least one stable brick in its four adjacent cells (left, right, up, down). We are also given a list of hits, which represent coordinates where we will remove bricks. Removing a brick might cause other bricks to lose their stability and fall. The key task is to calculate how many bricks fall after each hit. Bricks are removed instantly after the hit, so they don't fall on top of each other. It's important to note that if a hit points to an empty space, no bricks will fall as a result.

Intuition

To solve this problem, we employ a Union-Find algorithm—an efficient data structure to manage the connectivity among elements. We reverse the problem by adding bricks back in the reverse order of hits and tracking the change in the number of connected stable bricks.

We start by marking the bricks we'll hit to simulate the end state of the wall, where all specified hits have already occurred. We then use Union-Find to group the remaining stable bricks together. Notably, we add an extra node representing the 'roof', and we connect every top-row brick to this node, identifying them as stable since they are effectively connected to the roof.

Each hit is then processed in reverse. We first check if the brick was present before any hits occurred. If not, no bricks will fall. If it was, we add the brick back and connect it to its adjacent stable bricks, if any.

The ingenious part here is that by tracking the size of the sets that are connected to the roof node (stable bricks), we can easily compute the number of bricks that become unstable when a brick is removed. By reversing the hits, we're not removing bricks but checking the difference in the number of stable bricks through the root node before and after adding the brick back. The change in the size of the set lets us infer the number of bricks that would fall due to that hit.

Finally, we return the number of bricks that fall after each hit in the original order, which can be computed from the size differences observed when reverting the hits.

Learn more about Union Find patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Solution Approach

The provided Python code approach implements the Union-Find algorithm, also known as the Disjoint Set Union (DSU), to find connected components of bricks and determine their stability. Here's a step-by-step explanation of how the code approach works:

  1. Initial Setup:

    • Create a list p that represents the parent of each node (brick or cell) in the Union-Find data structure.
    • A special node m * n is added to represent the "roof" or top of the grid.
    • Create a list size to keep track of the size of each set (number of stable bricks connected together plus the roof).

  2. Preparing the Grid (g):

    • A copy of the original grid is made and modified such that all the bricks to be hit are removed, simulating the grid state after all hits.

  3. Union-Find Functions:

    • find(x): A recursive function that finds the representative (parent) of a set that the node x belongs to, with path compression optimization.
    • union(a, b): Connects two nodes a and b by pointing the representative of a to the representative of b and updating the size of the set.

  4. Stabilizing the Initial Grid:

    • All top-row bricks (first row) are connected to the roof in p.
    • Sequentially connect all other bricks to their upper or left neighbors (if those are bricks) using union.

  5. Processing Hits in Reverse:

    • Iterate through the list of hits in reverse.
    • If the grid initially had a brick at the hit location, revert the hit by restoring the brick.
    • For restoring, connect the brick to the roof if it's on the top row, and to its neighbors (if they're bricks) using union.
    • Record the change in the number of stable bricks connected to the roof to determine how many bricks would fall as a result of this hit.

  6. Recording the Changes:

    • For each hit, append to the ans list the difference in the number of stable bricks connected to the roof before and after the hit reversal, minus 1 (since we're adding the brick back, not removing it).

  7. Returning the Results:

    • Since the hits were processed in reverse, reverse the ans list to match the original order of hits and return it as the result.

By performing these steps, the code efficiently computes the number of bricks that will fall after each hit by keeping track of the size of connected stable components throughout the reverse sequence of hits.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement recursion?

Example Walkthrough

Let's illustrate the solution approach using a small example:

Suppose we have a 2D grid of bricks (1) and empty spaces (0) that looks like this:

1Grid:
21 0 1
31 1 1
40 1 0

And we are given a list of hits that represent coordinates where we will remove bricks: hits = [(0, 2), (2, 1)]. The coordinates are in the format (row, column).

  1. Initial Setup:

    • Assuming a 3x3 grid, we have 9 cells plus 1 for the roof, thus we create a list p of size 10 to represent parents. Initialize p such that p[i] = i for all i.
    • Create a list size of same length to track the size of each set.

  2. Preparing the Grid (g):

    • We modify the original grid to simulate the state after all hits:
1After hits:
21 0 0
31 1 0
40 0 0

  1. Stabilizing the Initial Grid:

    • Connect each top-row brick to the roof. In this case, it's the brick at (0, 0).
    • Connect every brick to its upper or left neighbor, unless it was removed. The grid remains the same since there are no additional top-row bricks and no connections to the left for this example.

  2. Processing Hits in Reverse:

    • Start with the last hit (2, 1). Since it is already empty, no bricks fall.
    • Next, process the hit (0, 2). Before this hit, the brick at (0, 2) was not connected to any other brick, therefore, no additional bricks fall.

  3. Recording the Changes:

    • When processing (2, 1), no bricks fall. We add 0 to the answer list.
    • For (0, 2), again no bricks fall. We also add 0 to the answer list.

  4. Returning the Results:

    • The results need to correspond to the hits in the original order (0, 2), (2, 1), and since we collected the counts in reverse, the answers list is [0, 0].

Hence, the final answer denoting how many bricks fall after each hit, in the original order, is [0, 0].

In this example, no bricks fall as a result of the hits since both hit locations are on top of an already stable structure or are empty spaces.

Solution Implementation

1class Solution:
2    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
3        # Helper function to find the root of set x
4        def find(x):
5            if parent[x] != x:
6                parent[x] = find(parent[x])
7            return parent[x]
8
9        # Helper function to perform union operation on sets containing a and b
10        def union(a, b):
11            root_a, root_b = find(a), find(b)
12            if root_a != root_b:
13                size[root_b] += size[root_a]
14                parent[root_a] = root_b
15
16        # Dimensions of the grid
17        rows, cols = len(grid), len(grid[0])
18      
19        # Initialize parent and size arrays for union-find
20        parent = list(range(rows * cols + 1))
21        size = [1] * (rows * cols + 1)
22
23        # Create a deep copy of the grid to reflect the initial hits
24        grid_copy = deepcopy(grid)
25        for i, j in hits:
26            grid_copy[i][j] = 0
27
28        # Connect the top row to the virtual top node
29        for j in range(cols):
30            if grid_copy[0][j] == 1:
31                union(j, rows * cols)
32
33        # Connect adjacent bricks in the grid_copy
34        for i in range(1, rows):
35            for j in range(cols):
36                if grid_copy[i][j] == 0:
37                    continue
38                if grid_copy[i - 1][j] == 1:
39                    union(i * cols + j, (i - 1) * cols + j)
40                if j > 0 and grid_copy[i][j - 1] == 1:
41                    union(i * cols + j, i * cols + j - 1)
42
43        # To store the number of bricks that fall after each hit
44        ans = []
45      
46        # Processing hits in reverse order
47        for i, j in reversed(hits):
48            if grid[i][j] == 0:
49                ans.append(0)
50                continue
51            grid_copy[i][j] = 1
52            prev_size = size[find(rows * cols)]
53          
54            # Connect the hit brick to adjacent bricks or the virtual top node
55            if i == 0:
56                union(j, rows * cols)
57            for delta_row, delta_col in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
58                x, y = i + delta_row, j + delta_col
59                if 0 <= x < rows and 0 <= y < cols and grid_copy[x][y] == 1:
60                    union(i * cols + j, x * cols + y)
61            curr_size = size[find(rows * cols)]
62          
63            # Calculate how many bricks fell
64            ans.append(max(0, curr_size - prev_size - 1))
65      
66        # Reverse the answer to return the correct order
67        return ans[::-1]
68
1class Solution {
2    private int[] parent;  // Array to store the parent of each element in the Union-Find data structure
3    private int[] size;    // Array to store the size of each set in the Union-Find data structure
4
5    public int[] hitBricks(int[][] grid, int[][] hits) {
6        int rows = grid.length;        // Total number of rows in the grid
7        int cols = grid[0].length;     // Total number of columns in the grid
8        parent = new int[rows * cols + 1]; // Initialize parent array, +1 is for the virtual root
9        size = new int[rows * cols + 1];   // Initialize size array, +1 is for the virtual root
10        for (int i = 0; i < parent.length; ++i) {
11            parent[i] = i; // Initially each element is its own parent
12            size[i] = 1;   // Initially the size of each set is 1
13        }
14
15        // Copy of the grid to modify and simulate hits
16        int[][] gridCopy = new int[rows][cols];
17        for (int i = 0; i < rows; ++i) {
18            for (int j = 0; j < cols; ++j) {
19                gridCopy[i][j] = grid[i][j];
20            }
21        }
22
23        // Apply hits to the grid copy
24        for (int[] hit : hits) {
25            gridCopy[hit[0]][hit[1]] = 0;
26        }
27      
28        // Union all stable bricks in the first row with the virtual root node
29        for (int j = 0; j < cols; ++j) {
30            if (gridCopy[0][j] == 1) {
31                union(j, rows * cols);
32            }
33        }
34
35        // Union all adjacent stable bricks in the rest of the grid
36        for (int i = 1; i < rows; ++i) {
37            for (int j = 0; j < cols; ++j) {
38                if (gridCopy[i][j] == 0) {
39                    continue;
40                }
41                if (gridCopy[i - 1][j] == 1) {
42                    union(i * cols + j, (i - 1) * cols + j);
43                }
44                if (j > 0 && gridCopy[i][j - 1] == 1) {
45                    union(i * cols + j, i * cols + j - 1);
46                }
47            }
48        }
49
50        // Result array to store the number of bricks that fall after each hit 
51        int[] result = new int[hits.length];
52        // Array to represent direction [up, right, down, left] as pairs
53        int[] dirs = {-1, 0, 1, 0, -1};
54      
55        // Reversely add back the bricks and union with neighbors if they are stable
56        for (int k = hits.length - 1; k >= 0; --k) {
57            int r = hits[k][0];
58            int c = hits[k][1];
59            if (grid[r][c] == 0) {
60                continue; // Skip, since there was no brick at (r, c) to begin with
61            }
62            gridCopy[r][c] = 1;
63
64            int prevSize = size[find(rows * cols)]; // Size of the top roof set before the union
65            if (r == 0) {
66                union(c, rows * cols); // Union first row brick with the virtual root
67            }
68
69            // Union the hit brick with its adjacent stable bricks
70            for (int l = 0; l < 4; ++l) {
71                int nr = r + dirs[l];
72                int nc = c + dirs[l + 1];
73                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && gridCopy[nr][nc] == 1) {
74                    union(r * cols + c, nr * cols + nc);
75                }
76            }
77            int currSize = size[find(rows * cols)]; // Size of the top roof set after the union
78            result[k] = Math.max(0, currSize - prevSize - 1); // Calculate fallen bricks not including the hit one
79        }
80
81        return result;
82    }
83
84    // Method to find the root of the set that element x belongs to
85    private int find(int x) {
86        if (parent[x] != x) {
87            parent[x] = find(parent[x]); // Path compression for efficiency
88        }
89        return parent[x];
90    }
91
92    // Method to union two sets that elements a and b belong to
93    private void union(int a, int b) {
94        int rootA = find(a);
95        int rootB = find(b);
96        if (rootA != rootB) {
97            size[rootB] += size[rootA]; // Merge the sets and update the size of the set
98            parent[rootA] = rootB;      // Make the root of A point to root of B
99        }
100    }
101}
102
1class Solution {
2public:
3    vector<int> parent;
4    vector<int> clusterSize;
5
6    // Main function to process the hitting of bricks.
7    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
8        int rows = grid.size(), cols = grid[0].size();
9        // Initialize the parent and clusterSize arrays.
10        parent.resize(rows * cols + 1);
11        clusterSize.resize(rows * cols + 1, 1);
12        for (int i = 0; i < parent.size(); ++i) {
13            parent[i] = i;
14        }
15
16        // Make a copy of the grid and apply the hits.
17        vector<vector<int>> currentGrid(rows, vector<int>(cols));
18        for (int i = 0; i < rows; ++i)
19            for (int j = 0; j < cols; ++j)
20                currentGrid[i][j] = grid[i][j];
21        for (auto& hit : hits) currentGrid[hit[0]][hit[1]] = 0;
22
23        // Connect the first row bricks to the virtual top node.
24        for (int j = 0; j < cols; ++j)
25            if (currentGrid[0][j] == 1)
26                merge(j, rows * cols);
27
28        // Connect the remaining bricks in the grid.
29        for (int i = 1; i < rows; ++i) {
30            for (int j = 0; j < cols; ++j) {
31                if (currentGrid[i][j] == 0) continue;
32                if (currentGrid[i - 1][j] == 1) merge(i * cols + j, (i - 1) * cols + j);
33                if (j > 0 && currentGrid[i][j - 1] == 1) merge(i * cols + j, i * cols + j - 1);
34            }
35        }
36
37        // Process the hits in reverse and calculate the results.
38        vector<int> results(hits.size());
39        vector<int> directions = {-1, 0, 1, 0, -1}; // Used for exploring adjacent cells.
40        for (int k = hits.size() - 1; k >= 0; --k) {
41            int i = hits[k][0], j = hits[k][1];
42            if (grid[i][j] == 0) continue; // The brick was already empty before the hit.
43
44            currentGrid[i][j] = 1; // Revert the hit.
45            int previousSize = clusterSize[findParent(rows * cols)];
46            // Connect the brick to the virtual top node if it's in the first row.
47            if (i == 0) merge(j, rows * cols);
48            // Connect the brick to its adjacent bricks.
49            for (int l = 0; l < 4; ++l) {
50                int x = i + directions[l], y = j + directions[l + 1];
51                if (x >= 0 && x < rows && y >= 0 && y < cols && currentGrid[x][y] == 1)
52                    merge(i * cols + j, x * cols + y);
53            }
54            int currentSize = clusterSize[findParent(rows * cols)];
55            // Calculate the number of bricks that fell due to the hit.
56            results[k] = max(0, currentSize - previousSize - 1);
57        }
58        return results;
59    }
60
61    // Find the root parent of a node, with path compression.
62    int findParent(int x) {
63        if (parent[x] != x) parent[x] = findParent(parent[x]);
64        return parent[x];
65    }
66
67    // Merge two clusters.
68    void merge(int a, int b) {
69        int rootA = findParent(a), rootB = findParent(b);
70        if (rootA != rootB) {
71            clusterSize[rootB] += clusterSize[rootA];
72            parent[rootA] = rootB;
73        }
74    }
75};
76
1// We use a flat array to represent the grid as a union find data structure.
2let parent: number[];
3let clusterSize: number[];
4
5// Function to find the root parent of a node with path compression.
6function findParent(x: number): number {
7    if (parent[x] !== x) parent[x] = findParent(parent[x]);
8    return parent[x];
9}
10
11// Function to merge two clusters.
12function merge(a: number, b: number): void {
13    let rootA = findParent(a),
14        rootB = findParent(b);
15
16    if (rootA !== rootB) {
17        clusterSize[rootB] += clusterSize[rootA];
18        parent[rootA] = rootB;
19    }
20}
21
22// Main function to process the hitting of bricks.
23function hitBricks(grid: number[][], hits: number[][]): number[] {
24    let rows = grid.length, cols = grid[0].length;
25  
26    // Initialize the parent and clusterSize arrays.
27    parent = new Array(rows * cols + 1);
28    clusterSize = new Array(rows * cols + 1).fill(1);
29    parent = parent.map((_, index) => index);
30
31    // Make a copy of the grid and apply the hits.
32    let currentGrid = grid.map(row => [...row]);
33    for (let hit of hits) currentGrid[hit[0]][hit[1]] = 0;
34
35    // Connect the first row bricks to the virtual top node.
36    for (let j = 0; j < cols; ++j) {
37        if (currentGrid[0][j] === 1) merge(j, rows * cols);
38    }
39
40    // Connect the remaining bricks in the grid.
41    for (let i = 1; i < rows; ++i) {
42        for (let j = 0; j < cols; ++j) {
43            if (currentGrid[i][j] === 0) continue;
44            if (currentGrid[i - 1][j] === 1) merge(i * cols + j, (i - 1) * cols + j);
45            if (j > 0 && currentGrid[i][j - 1] === 1) merge(i * cols + j, i * cols + j - 1);
46        }
47    }
48
49    // Process the hits in reverse and calculate the results.
50    let results = new Array(hits.length).fill(0),
51        directions = [-1, 0, 1, 0, -1]; // Used for exploring adjacent cells.
52
53    for (let k = hits.length - 1; k >= 0; --k) {
54        let i = hits[k][0], j = hits[k][1];
55        if (grid[i][j] === 0) continue; // The brick was already empty before the hit.
56
57        currentGrid[i][j] = 1; // Revert the hit.
58        let previousSize = clusterSize[findParent(rows * cols)];
59
60        // Connect the brick to the virtual top node if it's in the first row.
61        if (i === 0) merge(j, rows * cols);
62
63        // Connect the brick to its adjacent bricks.
64        for (let l = 0; l < 4; ++l) {
65            let x = i + directions[l], y = j + directions[l + 1];
66            if (x >= 0 && x < rows && y >= 0 && y < cols && currentGrid[x][y] === 1)
67                merge(i * cols + j, x * cols + y);
68        }
69
70        let currentSize = clusterSize[findParent(rows * cols)];
71        // Calculate the number of bricks that fell due to the hit.
72        results[k] = Math.max(0, currentSize - previousSize - 1);
73    }
74
75    return results;
76}
77
Not Sure What to Study? Take the 2-min Quiz：

Which two pointer technique does Quick Sort use?

Time and Space Complexity

Time Complexity

The time complexity of the function is determined by several nested loops and the use of the union-find algorithm.

  1. Initialization: Initializing the parent array p and size array size takes O(m*n) time, where m is the number of rows and n is the number of columns in the grid.
  2. Deep Copy: The deep copy of the grid g = deepcopy(grid) takes O(m*n) time.
  3. First Pass: The first two nested loops which connect the top row bricks and the rest of the bricks to their respective parents take O(m*n*α(m*n)) time, where α is the Inverse Ackermann function which is a very slow-growing function that is considered almost constant in practice for any conceivable grid size.
  4. Processing Hits: The main for-loop that processes the hits is O(k*m*n*α(m*n)), where k is the number of hits. This is because for each hit, it may potentially union with 4 neighboring bricks.
  5. Reversing the Answer: Lastly, reversing the answer list at the end takes O(k) time.

Combining these components, the overall time complexity is O(m*n + k*m*n*α(m*n)).

Space Complexity

The space complexity is determined by the storage used:

  1. Union-Find Structures: The parent array p and size array size take O(m*n) space.
  2. Grid Copy: The deep copy of the grid takes O(m*n) space.
  3. Answers List: The answer array ans takes O(k) space where k is the number of hits.
  4. Auxiliary Space: There is additional auxiliary space used for various variables which do not depend on the size of the grid or the number of hits.

Thus, the overall space complexity is O(m*n) as this is the most significant space requirement.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Recommended Readings

DSU/Union Find Fundamentals

Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫