Skip to content

803. Bricks Falling When Hit 👍

  • Time: $O(mn |\texttt{hits}| \log(mn |\texttt{hits}|))$
  • Space: $O(mn)$
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
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;
  }
};

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
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;
  }
}