Bricks Falling When Hit

Hard

Asked by:

37 views

Topics:

ArraysGraphs

You are given an m x n binary grid, where each 1 represents a brick and 0 represents an empty space. A brick is 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.

You are also given an array hits, which is a sequence of erasures we want to apply. Each time we want to erase the brick at the location hits[i] = (row_i, col_i). The brick on that location (if it exists) will disappear. Some other bricks may no longer be stable because of that erasure and will fall. Once a brick falls, it is immediately erased from the grid (i.e., it does not land on other stable bricks).

Return an array result, where each result[i] is the number of bricks that will fall after the i^th erasure is applied.

Note that an erasure may refer to a location with no brick, and if it does, no bricks drop.

Example 1:

Input: grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
Output: [2]
Explanation: Starting with the grid:
[[1,0,0,0],
 [1,1,1,0]]
We erase the underlined brick at (1,0), resulting in the grid:
[[1,0,0,0],
 [0,1,1,0]]
The two underlined bricks are no longer stable as they are no longer connected to the top nor adjacent to another stable brick, so they will fall. The resulting grid is:
[[1,0,0,0],
 [0,0,0,0]]
Hence the result is [2].

Example 2:

Input: grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
Output: [0,0]
Explanation: Starting with the grid:
[[1,0,0,0],
 [1,1,0,0]]
We erase the underlined brick at (1,1), resulting in the grid:
[[1,0,0,0],
 [1,0,0,0]]
All remaining bricks are still stable, so no bricks fall. The grid remains the same:
[[1,0,0,0],
 [1,0,0,0]]
Next, we erase the underlined brick at (1,0), resulting in the grid:
[[1,0,0,0],
 [0,0,0,0]]
Once again, all remaining bricks are still stable, so no bricks fall.
Hence the result is [0,0].

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 200
grid[i][j] is 0 or 1.
1 <= hits.length <= 4 * 10⁴
hits[i].length == 2
0 <= x_i<= m - 1
0 <= y_i <= n - 1
All (x_i, y_i) are unique.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the `grid`, and what's the maximum value for `hits` length?
Are the bricks initially connected, meaning is there always a path from each brick to the top of the grid before any hits occur?
If a hit causes multiple bricks to fall, do I need to calculate and return the number of bricks falling *after* each individual hit, or after *all* hits have been processed?
Are the coordinates in `hits` guaranteed to be within the bounds of the `grid`?
Is the top row (row index 0) considered connected to the ceiling, or does a brick need to be directly adjacent to the edge to be supported?

Brute Force Solution

Approach

The brute force way to solve this is to simulate removing each brick one by one. After removing each brick, we check which bricks are still connected to the top. The bricks that aren't connected to the top will fall.

Here's how the algorithm would work step-by-step:

For each brick that we hit, temporarily remove it from the structure.
After removing a brick, check every single remaining brick to see if it's still connected to the top layer of the structure.
A brick is considered 'connected' if there is a path of bricks touching each other all the way from that brick to the top layer.
Any brick that is not connected to the top is considered to have fallen. Count those bricks.
After counting the fallen bricks, put the brick we temporarily removed back into the structure.
Move on to the next brick that we hit, and repeat the process.

Code Implementation

def bricks_falling_when_hit_brute_force(grid, hits):
    rows = len(grid)
    cols = len(grid[0])
    results = []

    def is_valid(row_coordinate, col_coordinate):
        return 0 <= row_coordinate < rows and 0 <= col_coordinate < cols

    def is_connected(grid_copy, row_coordinate, col_coordinate, visited):
        if not is_valid(row_coordinate, col_coordinate) or grid_copy[row_coordinate][col_coordinate] == 0 or (row_coordinate, col_coordinate) in visited:
            return False

        if row_coordinate == 0:
            return True

        visited.add((row_coordinate, col_coordinate))

        # Check adjacent cells
        neighbors = [(row_coordinate + 1, col_coordinate), (row_coordinate - 1, col_coordinate),
                     (row_coordinate, col_coordinate + 1), (row_coordinate, col_coordinate - 1)]

        for neighbor_row, neighbor_col in neighbors:
            if is_connected(grid_copy, neighbor_row, neighbor_col, visited):
                return True

        return False

    def count_fallen_bricks(grid_copy):
        fallen_count = 0
        for row_coordinate in range(rows):
            for col_coordinate in range(cols):
                if grid_copy[row_coordinate][col_coordinate] == 1:
                    visited = set()
                    if not is_connected(grid_copy, row_coordinate, col_coordinate, visited):
                        fallen_count += 1
        return fallen_count

    for hit in hits:
        row_to_remove, col_to_remove = hit
        
        # Temporarily remove the brick
        original_value = grid[row_to_remove][col_to_remove]
        grid[row_to_remove][col_to_remove] = 0
        
        grid_copy = [row[:] for row in grid] # Create a copy for simulation

        fallen_bricks = count_fallen_bricks(grid_copy)
        results.append(fallen_bricks)

        # Restore the brick for the next iteration
        grid[row_to_remove][col_to_remove] = original_value

    return results

Big(O) Analysis

Time Complexity

O(m * n) – Let m be the number of hits and n be the number of bricks. For each of the m hits, we temporarily remove a brick. Then, for each of the remaining bricks (n bricks in the worst case), we perform a connectivity check to the top layer. The connectivity check itself could involve visiting each brick in the worst case. Therefore, the time complexity for a single hit is O(n), and since we do this for each of the m hits, the overall time complexity is O(m * n).

Space Complexity

O(N) – The algorithm's space complexity stems primarily from the need to check for connectivity to the top layer for each brick. This connectivity check, although not explicitly stated, would likely involve a Depth-First Search (DFS) or Breadth-First Search (BFS). In the worst-case scenario, where all bricks are connected, the recursion stack (for DFS) or the queue (for BFS) could grow up to the number of bricks, which we can denote as N. Therefore, the auxiliary space used scales linearly with the number of bricks, resulting in a space complexity of O(N).

Optimal Solution

Approach

The key is to reverse the problem. Instead of figuring out which bricks fall when hit, we start with the end state (after all hits) and rebuild the structure, determining which bricks must be stable based on being connected to the top.

Here's how the algorithm would work step-by-step:

First, consider the situation after all the hits have occurred. Mark all the bricks that are still present.
Next, start by identifying which bricks are directly connected to the top. These are definitely stable.
Then, identify any other bricks that are connected to these stable top bricks. These are also stable.
Continue finding bricks that are connected to already stable bricks, marking them as stable. Repeat until no new bricks can be marked as stable.
Now, go through the list of hit locations. For each hit, figure out how many bricks were present before the hit but are not present (and therefore, not stable) in the final state. These are the bricks that would have fallen because of that hit.
Return the list of the number of falling bricks for each hit.

Code Implementation

def falling_bricks(grid, hits):
    rows = len(grid)
    columns = len(grid[0])
    hit_results = []

    # Mark bricks to be removed for simulation
    for row_index, column_index in hits:
        if grid[row_index][column_index] == 1:
            grid[row_index][column_index] = 2

    def perform_depth_first_search(row_index, column_index, stable_bricks):
        if (row_index < 0 or row_index >= rows or
            column_index < 0 or column_index >= columns or
            grid[row_index][column_index] != 1 or
            (row_index, column_index) in stable_bricks):
            return

        stable_bricks.add((row_index, column_index))

        perform_depth_first_search(row_index + 1, column_index, stable_bricks)
        perform_depth_first_search(row_index - 1, column_index, stable_bricks)
        perform_depth_first_search(row_index, column_index + 1, stable_bricks)
        perform_depth_first_search(row_index, column_index - 1, stable_bricks)

    # Find stable bricks connected to the top
    stable_bricks_set = set()
    for column_index in range(columns):
        if grid[0][column_index] == 1:
            perform_depth_first_search(0, column_index, stable_bricks_set)

    # Process hits in reverse order to rebuild
    for row_index, column_index in reversed(hits):
        if grid[row_index][column_index] == 2:
            grid[row_index][column_index] = 1
        else:
            hit_results.append(0)
            continue

        initial_stable_count = len(stable_bricks_set)

        # Check if the brick can become stable
        perform_depth_first_search(row_index, column_index, stable_bricks_set)

        # Determine number of new bricks made stable.
        newly_stable_count = len(stable_bricks_set) - initial_stable_count
        hit_results.append(newly_stable_count)

    # Restore grid state and reverse hit_results
    for row_index, column_index in hits:
        if grid[row_index][column_index] == 2:
            grid[row_index][column_index] = 0

    hit_results.reverse()
    return hit_results

Big(O) Analysis

Time Complexity

O(R * C * H) – The algorithm reverses the hits and rebuilds the brick structure. Identifying stable bricks connected to the top involves traversing the grid, potentially visiting each cell multiple times. The number of stable brick checks for each hit location depends on the grid's dimensions (R rows, C columns) and the number of hits (H). In the worst case, the connected component search could iterate through most of the grid for each hit. Therefore, the time complexity is proportional to the grid size (R * C) multiplied by the number of hits (H), leading to O(R * C * H).

Space Complexity

O(R * C) – The algorithm uses extra space primarily for representing the grid and tracking stable bricks. The grid, and potentially a separate grid to mark stable bricks, has dimensions corresponding to the number of rows (R) and columns (C) of the input bricks grid. Additionally, the connected components search may use a queue or recursion stack whose size in the worst case depends on the number of cells in the grid. Therefore, the auxiliary space is proportional to R * C, where R is the number of rows and C is the number of columns of the grid, which represents the dimensions of the brick structure.

Edge Cases

Case	How to Handle
Empty grid or no bricks to hit	Return empty array if grid is empty or hits array is empty.
Grid is a single row or single column	Ensure correct handling of connectivity checks on the boundary when grid is very narrow.
All bricks are hit	The number of remaining bricks will rapidly decrease, potentially to zero.
Hits outside the grid bounds	Ignore hits that fall outside the grid boundaries to avoid array out of bounds errors.
Multiple hits on the same brick	Ensure the algorithm only counts the brick removal once even if hit multiple times.
Large grid dimensions	Optimize memory usage and algorithm complexity to avoid timeouts or memory errors on larger grids.
Bricks initially not connected to the top	These bricks should fall regardless of hits elsewhere, so ensure initial setup handles them correctly.
Integer overflow when calculating connected components	Use appropriate data types (e.g., long) to avoid overflow issues when counting connected bricks.

Empty grid or no bricks to hit

How to Handle:

Return empty array if grid is empty or hits array is empty.

Grid is a single row or single column

How to Handle:

Ensure correct handling of connectivity checks on the boundary when grid is very narrow.

All bricks are hit

How to Handle:

The number of remaining bricks will rapidly decrease, potentially to zero.

Hits outside the grid bounds

How to Handle:

Ignore hits that fall outside the grid boundaries to avoid array out of bounds errors.

Multiple hits on the same brick

How to Handle:

Ensure the algorithm only counts the brick removal once even if hit multiple times.

Large grid dimensions

How to Handle:

Optimize memory usage and algorithm complexity to avoid timeouts or memory errors on larger grids.

Bricks initially not connected to the top

How to Handle:

These bricks should fall regardless of hits elsewhere, so ensure initial setup handles them correctly.

Integer overflow when calculating connected components

How to Handle:

Use appropriate data types (e.g., long) to avoid overflow issues when counting connected bricks.