In this guide, you will get 803. Bricks Falling When Hit LeetCode Solution with the best time and space complexity. The solution to Bricks Falling When Hit problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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] = (rowi, coli). 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 ith 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].
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 * 104
hits[i].length == 2
0 <= xi <= m – 1
0 <= yi <= n – 1
All (xi, yi) are unique.
Complexity Analysis
Time Complexity: O(mn |\texttt{hits}| \log(mn |\texttt{hits}|))
Space Complexity: O(mn)
803. Bricks Falling When Hit LeetCode Solution in C++
class UnionFind {
public:
UnionFind(int n) : id(n), sz(n, 1) {
iota(id.begin(), id.end(), 0);
}
void unionBySize(int u, int v) {
const int i = find(u);
const int j = find(v);
if (i == j)
return;
if (sz[i] < sz[j]) {
sz[j] += sz[i];
id[i] = j;
} else {
sz[i] += sz[j];
id[j] = i;
}
}
int getStableSize() {
// Bricks connected with 0 (top) are stable.
return sz[find(0)];
}
private:
vector<int> id;
vector<int> sz;
int find(int u) {
return id[u] == u ? u : id[u] = find(id[u]);
}
};
class Solution {
public:
vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
m = grid.size();
n = grid[0].size();
UnionFind uf(m * n + 1); // 0 := top (stable)
// Mark cells to hit as 2.
for (const vector<int>& hit : hits) {
const int i = hit[0];
const int j = hit[1];
if (grid[i][j] == 1)
grid[i][j] = 2;
}
// Union all the 1s.
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 1)
unionNeighbors(grid, uf, i, j);
vector<int> ans(hits.size());
int stableSize = uf.getStableSize();
for (int i = hits.size() - 1; i >= 0; --i) {
const int x = hits[i][0];
const int y = hits[i][1];
if (grid[x][y] == 2) { // cells marked from 1 to 2
grid[x][y] = 1; // Unhit and restore it back to 1.
unionNeighbors(grid, uf, x, y);
const int newStableSize = uf.getStableSize();
if (newStableSize > stableSize)
ans[i] = newStableSize - stableSize - 1; // 1 := the hit cell
stableSize = newStableSize;
}
}
return ans;
}
private:
static constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int m;
int n;
void unionNeighbors(const vector<vector<int>>& grid, UnionFind& uf, int i,
int j) {
const int hash = getHash(i, j);
for (const auto& [dx, dy] : dirs) {
const int x = i + dx;
const int y = j + dy;
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (grid[x][y] != 1)
continue;
uf.unionBySize(hash, getHash(x, y));
}
if (i == 0)
uf.unionBySize(hash, 0);
}
int getHash(int i, int j) {
return i * n + j + 1;
}
}; /* code provided by PROGIEZ */
803. Bricks Falling When Hit LeetCode Solution in Java
class UnionFind {
public UnionFind(int n) {
id = new int[n];
sz = new int[n];
for (int i = 0; i < n; ++i)
id[i] = i;
Arrays.fill(sz, 1);
}
public void unionBySize(int u, int v) {
final int i = find(u);
final int j = find(v);
if (i == j)
return;
if (sz[i] < sz[j]) {
sz[j] += sz[i];
id[i] = j;
} else {
sz[i] += sz[j];
id[j] = i;
}
}
public int getStableSize() {
// Bricks connected with 0 (top) are stable.
return sz[find(0)];
}
private int[] id;
private int[] sz;
private int find(int u) {
return id[u] == u ? u : (id[u] = find(id[u]));
}
}
class Solution {
public int[] hitBricks(int[][] grid, int[][] hits) {
this.m = grid.length;
this.n = grid[0].length;
UnionFind uf = new UnionFind(m * n + 1); // 0 := top (stable)
// Mark cells to hit as 2.
for (int[] hit : hits) {
final int i = hit[0];
final int j = hit[1];
if (grid[i][j] == 1)
grid[i][j] = 2;
}
// Union all the 1s.
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 1)
unionNeighbors(grid, uf, i, j);
int[] ans = new int[hits.length];
int stableSize = uf.getStableSize();
for (int i = hits.length - 1; i >= 0; --i) {
final int x = hits[i][0];
final int y = hits[i][1];
if (grid[x][y] == 2) { // cells marked from 1 to 2
grid[x][y] = 1; // Unhit and restore it back to 1.
unionNeighbors(grid, uf, x, y);
final int newStableSize = uf.getStableSize();
if (newStableSize > stableSize)
ans[i] = newStableSize - stableSize - 1; // 1 := the hit cell
stableSize = newStableSize;
}
}
return ans;
}
private int m;
private int n;
private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private void unionNeighbors(int[][] grid, UnionFind uf, int i, int j) {
final int hash = getHash(i, j);
for (int[] dir : dirs) {
final int x = i + dir[0];
final int y = j + dir[1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (grid[x][y] != 1)
continue;
uf.unionBySize(hash, getHash(x, y));
}
if (i == 0)
uf.unionBySize(hash, 0);
}
private int getHash(int i, int j) {
return i * n + j + 1;
}
} // code provided by PROGIEZ
803. Bricks Falling When Hit LeetCode Solution in Python
