What is the time complexity of Bricks Falling When Hit?

The optimal solution has a time complexity of O(m*n*alpha(m*n) + k).

What is the space complexity of Bricks Falling When Hit?

The space complexity is O(m*n).

What data structures are used to solve Bricks Falling When Hit?

This problem uses Array, Union Find, Matrix. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Bricks Falling When Hit?

Insight 1: The key is to process the hits in reverse order. Instead of removing bricks, we add them back. This transforms the problem into finding how many bricks become stable with each addition. Insight 2: Union Find is an appropriate data structure for tracking connected components (stable bricks). We can use it to efficiently determine which bricks are connected to the top row after adding a brick back.

Which companies ask LeetCode 803. Bricks Falling When Hit in interviews?

This problem is frequently asked at Snap, Tower Research Capital.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Bricks Falling When Hit - LeetCode 803 Solution

Bricks Falling When Hit - Complete Solution Guide

Bricks Falling When Hit is LeetCode problem 803, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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

Detailed Explanation

The problem describes a scenario where we have a grid of bricks, represented by 1s and empty spaces by 0s. Some bricks are 'stable' if they are connected to the top row or connected to another stable brick. We are given a list of 'hits' which represent locations where bricks are erased. The goal is to return an array where each element represents the number of bricks that fall as a result of each hit. It's important to note that a brick can fall only if it's no longer connected to the top or adjacent to another stable brick, and a 'hit' on an empty space causes no bricks to fall.

Solution Approach

The solution uses the Union Find data structure to efficiently track connected components of stable bricks. The crucial part is processing the 'hits' in reverse order. This transforms the problem of removing bricks and figuring out which ones fall, to adding bricks back and figuring out how many become stable because of it. The Union Find operations help determine how many bricks get connected to the 'top' connected component, and from this, we can determine how many bricks would have fallen if that brick had been hit.

Step-by-Step Algorithm

Step 1: Create a copy of the original grid. Apply all the hits to this copy (set the hit positions to 0). This gives us the 'grid after hits'.
Step 2: Initialize the Union Find data structure. Each brick in the 'grid after hits' is initially its own component. The 'parent' array represents this, and the 'size' array tracks the size of each component.
Step 3: Create a 'dummy' top node. All bricks in the first row of the 'grid after hits' are connected to this top node using the Union Find 'union' operation.
Step 4: Iterate through the rest of the 'grid after hits'. For each brick, check its neighbors (up, down, left, right). If a neighbor is also a brick, connect them using the Union Find 'union' operation.
Step 5: Process the 'hits' in *reverse* order. For each hit (r, c):
Step 6: If the original grid had a brick at (r, c):
Step 7: Record the size of the connected component containing the top node *before* adding the brick back.
Step 8: Add the brick back to the 'grid after hits' (set grid_after_hits[r][c] = 1).
Step 9: Connect the brick to the top node if it's in the first row.
Step 10: Connect the brick to its neighbors (up, down, left, right) that are also bricks using Union Find.
Step 11: Record the size of the connected component containing the top node *after* adding the brick back.
Step 12: The number of bricks that 'fall' as a result of this hit is the *difference* between the 'after' size and the 'before' size, minus 1 (to exclude the hit brick itself). If the difference is negative, then return 0.
Step 13: If the original grid *didn't* have a brick at (r, c), then 0 bricks fall.
Step 14: Store the fallen brick count in the 'result' array.
Step 15: Reverse the 'result' array to get the correct order corresponding to the original order of hits.

Key Insights

Insight 1: The key is to process the hits in reverse order. Instead of removing bricks, we add them back. This transforms the problem into finding how many bricks become stable with each addition.
Insight 2: Union Find is an appropriate data structure for tracking connected components (stable bricks). We can use it to efficiently determine which bricks are connected to the top row after adding a brick back.
Insight 3: A 'dummy' top node helps simplify the union-find process. By connecting all bricks in the top row to this node, we can easily check if a brick is connected to the top.
Insight 4: Avoid double counting the hit brick itself. The fallen count should be the *increase* in the size of the top connected component *excluding* the hit brick that was just added.

Complexity Analysis

Time Complexity: O(m*n*alpha(m*n) + k)

Space Complexity: O(m*n)

Topics

This problem involves: Array, Union Find, Matrix.

Companies

Asked at: Snap, Tower Research Capital.

Bricks Falling When Hit | LeetCode 803

Hard

Array Union Find Matrix

Time: O(m*n*alpha(m*n) + k)Space: O(m*n)

Solution Code

Available in:

class Solution {
    public int[] hitBricks(int[][] grid, int[][] hits) {
        int m = grid.length;
        int n = grid[0].length;

        int[] parent = new int[m * n + 1];
        int[] size = new int[m * n + 1];
        int TOP_NODE = m * n;

        for (int i = 0; i <= m * n; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        function find = (i) -> {
            if (parent[i] == i) {
                return i;
            }
            parent[i] = find.apply(parent[i]);
            return parent[i];
        };

        function union = (i, j) -> {
            int root_i = find.apply(i);
            int root_j = find.apply(j);
            if (root_i != root_j) {
                if (size[root_i] < size[root_j]) {
                    int temp = root_i;
                    root_i = root_j;
                    root_j = temp;
                }
                parent[root_j] = root_i;
                size[root_i] += size[root_j];
            }
        };

        function get_index = (r, c) -> {
            return r * n + c;
        };

        int[][] grid_after_hits = new int[m][n];
        for (int i = 0; i < m; i++) {
            grid_after_hits[i] = grid[i].clone();
        }
        
        for (int[] hit : hits) {
            int r = hit[0];
            int c = hit[1];
            grid_after_hits[r][c] = 0;
        }

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid_after_hits[r][c] == 1) {
                    int idx = get_index.apply(r, c);
                    if (r == 0) {
                        union.apply(idx, TOP_NODE);
                    }
                    if (r > 0 && grid_after_hits[r - 1][c] == 1) {
                        union.apply(idx, get_index.apply(r - 1, c));
                    }
                    if (c > 0 && grid_after_hits[r][c - 1] == 1) {
                        union.apply(idx, get_index.apply(r, c - 1));
                    }
                }
            }
        }

        int[] result = new int[hits.length];
        for (int i = hits.length - 1; i >= 0; i--) {
            int r = hits[i][0];
            int c = hits[i][1];

            if (grid[r][c] == 0) {
                result[i] = 0;
                continue;
            }

            int stable_before = size[find.apply(TOP_NODE)];

            int idx = get_index.apply(r, c);
            grid_after_hits[r][c] = 1;

            if (r == 0) {
                union.apply(idx, TOP_NODE);
            }

            int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            for (int[] dir : directions) {
                int dr = dir[0];
                int dc = dir[1];
                int nr = r + dr;
                int nc = c + dc;
                if (0 <= nr && nr < m && 0 <= nc && nc < n && grid_after_hits[nr][nc] == 1) {
                    union.apply(idx, get_index.apply(nr, nc));
                }
            }

            int stable_after = size[find.apply(TOP_NODE)];

            int fallen_count = Math.max(0, stable_after - stable_before - 1);
            result[i] = fallen_count;
        }

        int[] reversed_result = new int[hits.length];
        for (int i = 0; i < hits.length; i++) {
            reversed_result[i] = result[hits.length - 1 - i];
        }

        return reversed_result;
    }

    interface function {
        int apply(int i);
        int apply(int r, int c);
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 803: Bricks Falling When Hit - Detailed explanation and solution approaches.

Topics

Array Union Find Matrix

Companies

SnapTower Research Capital

Stats

Difficulty:Hard

Languages:4

Companies:2

Problem #:803

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

15 steps

1
Step 1: Create a copy of the original grid. Apply all the hits to this copy (set the hit positions to 0). This gives us the 'grid after hits'.
2
Step 2: Initialize the Union Find data structure. Each brick in the 'grid after hits' is initially its own component. The 'parent' array represents this, and the 'size' array tracks the size of each component.
3
Step 3: Create a 'dummy' top node. All bricks in the first row of the 'grid after hits' are connected to this top node using the Union Find 'union' operation.
4
Step 4: Iterate through the rest of the 'grid after hits'. For each brick, check its neighbors (up, down, left, right). If a neighbor is also a brick, connect them using the Union Find 'union' operation.
5
Step 5: Process the 'hits' in *reverse* order. For each hit (r, c):
6
Step 6: If the original grid had a brick at (r, c):
7
Step 7: Record the size of the connected component containing the top node *before* adding the brick back.
8
Step 8: Add the brick back to the 'grid after hits' (set grid_after_hits[r][c] = 1).
9
Step 9: Connect the brick to the top node if it's in the first row.
10
Step 10: Connect the brick to its neighbors (up, down, left, right) that are also bricks using Union Find.
11
Step 11: Record the size of the connected component containing the top node *after* adding the brick back.
12
Step 12: The number of bricks that 'fall' as a result of this hit is the *difference* between the 'after' size and the 'before' size, minus 1 (to exclude the hit brick itself). If the difference is negative, then return 0.
13
Step 13: If the original grid *didn't* have a brick at (r, c), then 0 bricks fall.
14
Step 14: Store the fallen brick count in the 'result' array.
15
Step 15: Reverse the 'result' array to get the correct order corresponding to the original order of hits.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(m*n*alpha(m*n) + k)

💾

Space Complexity

O(m*n)

📝

Why?

The Union Find operations (find and union) take amortized O(alpha(m*n)) time each due to path compression and union by rank. The grid copying and result array contribute O(m*n) space.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Depth-First Search (DFS)

For each hit, we could perform DFS to identify the connected component connected to the top row and count the number of fallen bricks. This approach will likely timeout.

Time: O(k * m * n) in the worst case, where k is the number of hits.Space: O(m * n) due to the recursion stack in DFS.

Trade-offs: DFS is easier to understand conceptually, but it is significantly less efficient than Union Find for this problem, especially with the given constraints. The high time complexity means DFS is unlikely to pass the time limit on larger test cases.

✨

Key Insights

1Insight 1: The key is to process the hits in reverse order. Instead of removing bricks, we add them back. This transforms the problem into finding how many bricks become stable with each addition.
2Insight 2: Union Find is an appropriate data structure for tracking connected components (stable bricks). We can use it to efficiently determine which bricks are connected to the top row after adding a brick back.
3Insight 3: A 'dummy' top node helps simplify the union-find process. By connecting all bricks in the top row to this node, we can easily check if a brick is connected to the top.
4Insight 4: Avoid double counting the hit brick itself. The fallen count should be the *increase* in the size of the top connected component *excluding* the hit brick that was just added.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Edge Cases

Edge case 1: Hitting a cell that is already empty. The code correctly handles this case by checking if `grid[r][c] == 0` and appending 0 to the result.
Edge case 2: A brick falls but connects to the 'top' node through a different path during the reverse addition process. The Union Find algorithm correctly identifies this new path and accounts for the additional stable bricks.
Edge case 3: Hitting a brick in the first row. The code correctly connects this brick to the TOP_NODE during the reverse addition, ensuring it's considered stable.
Edge case 4: No bricks fall after a hit. The code correctly calculates fallen_count as max(0, stable_after - stable_before - 1), ensuring a non-negative result.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Processing the hits in the original order. This approach is much harder to implement correctly as it requires identifying which bricks are no longer stable after each removal.

✗Common mistake 2: Failing to exclude the hit brick itself when calculating the number of fallen bricks. The fallen_count should only include bricks that become stable because of the hit brick being added back.

✗Common mistake 3: Not handling the edge case where the hit location is not a brick in the original grid (i.e., a 0).

✗Common mistake 4: Forgetting to reverse the result array after processing the hits in reverse order.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Network connectivity. This algorithm can be adapted to model the robustness of a network. Imagine bricks as nodes in a network, and hits as failures of nodes. The algorithm could determine the impact of each node failure on the overall network connectivity.

🏦Real-world scenario 2: Structural integrity. The problem models the stability of a structure composed of interconnected components (bricks). The hits represent the removal of support structures. The algorithm can assess the impact of removing support structures on the stability of the whole.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

These problems test your ability to optimize. Start with a brute force solution, then improve.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 23, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 14

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 7

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jun 30

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

Is it okay to not fully solve hard problems in interviews?

Yes! Interviewers care more about your problem-solving process than the final answer. Demonstrate: clear communication, systematic approach, ability to recognize when to pivot strategies, and graceful handling of hints. Partial progress with good reasoning is valued.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Bricks Falling When Hit"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether union find techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?