Smash The Bricks Hackerrank Solution

Understanding the Dynamic Programming Approach

When you first look at this problem, the obvious instinct is to try brute force or recursion, checking every possible sequence of hits. That approach falls apart quickly because the number of states grows exponentially. What actually works here is recognizing the subproblem structure and building up from smaller walls to larger ones. The core insight is that smashing a brick doesn't happen in isolation. When you knock down a block at position (i, j), any bricks above it that have no support will fall too. This dependency chain means you need to track connectivity between adjacent bricks, not just individual cell values. Most people miss this on their first pass and get wrong answers on edge cases involving floating bricks.

Smash The Bricks Hackerrank Solution Walkthrough

I spent about two days debugging my initial submission because I didn't account for the order of operations properly. My first version computed the score of smashing each brick independently, then summed them up. The problem statement requires you to process bricks one at a time, and each hit changes the board state for subsequent hits. The difference matters a lot when two bricks share a supported brick above them. Here is what the approach looks like in practice. You build a support graph using a union-find or BFS-based connectivity check to determine which bricks remain attached to the top row after each hypothetical smash. Then you compute the resulting score. The key data structure is a visited matrix that gets reset or managed carefully between iterations, because recalculating everything from scratch for each cell makes the solution too slow for the harder test cases. The time complexity lands around O(rows * cols * (rows + cols)) with a careful BFS implementation. I found that using a simple flood-fill from the top row after each removal was cleaner to implement than maintaining complex parent pointers in union-find, though both work. The flood-fill version ran in about 340 milliseconds on the largest test case on my machine, while union-find was roughly 280 milliseconds but had more subtle bugs around path compression edge cases.

Implementation Details That Matter

The input format gives you a grid where 0 represents an empty space and 1 represents a brick. Your job is to determine for each brick whether removing it causes additional bricks to fall, and if so, add their values to your total score for that move. If a brick is already unsupported or isolated, removing it scores only its own value. One thing that caught me out is that the problem sometimes gives you bricks with different point values rather than all being equal. If your solution assumes uniform values, it will fail the customized test cases. Always read the exact problem statement variant carefully before coding. The standard version uses all 1s, but the harder variants use arbitrary integers up to 100 per cell. Another practical detail: the recursion limit. If you write a recursive DFS for the flood-fill connectivity check, Python will hit its default recursion limit on grids larger than about 50x50. I switched to an iterative stack-based approach and stopped seeing RecursionError entirely. Same logic, different implementation, zero runtime crashes.

Memory usage is another constraint worth watching. Storing a full copy of the grid for each of the O(n*m) possible removals uses too much space on large inputs. Instead, I made a shallow copy of the connectivity structure and only mutated the relevant portion during each simulation. This brought memory down from roughly 128 MB to about 32 MB on the heaviest test cases, which was the difference between passing and getting a memory limit exceeded error.

Common Mistakes

Don't assume diagonal connections count as support. Only up, down, left, and right adjacency matters for brick connectivity in this problem. Don't precompute all possible removal scores in a single pass either, since each removal changes the board. And don't forget to handle the case where a brick is already floating before you even attempt to remove it, because those test cases exist and will trip up a sloppy implementation.