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(begin(id), end(id), 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 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, restore 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:
  const vector<int> dirs{0, 1, 0, -1, 0};
  int m;
  int n;

  void unionNeighbors(const vector<vector<int>>& grid, UnionFind& uf, int i,
                      int j) {
    const int hashed = hash(i, j);

    for (int k = 0; k < 4; ++k) {
      const int x = i + dirs[k];
      const int y = j + dirs[k + 1];
      if (x < 0 || x == m || y < 0 || y == n)
        continue;
      if (grid[x][y] != 1)
        continue;
      uf.unionBySize(hashed, hash(x, y));
    }

    if (i == 0)
      uf.unionBySize(hashed, 0);
  }

  int hash(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 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, restore 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, 0, -1, 0};

  private void unionNeighbors(int[][] grid, UnionFind uf, int i, int j) {
    final int hashed = hash(i, j);

    for (int k = 0; k < 4; ++k) {
      final int x = i + dirs[k];
      final int y = j + dirs[k + 1];
      if (x < 0 || x == m || y < 0 || y == n)
        continue;
      if (grid[x][y] != 1)
        continue;
      uf.unionBySize(hashed, hash(x, y));
    }

    if (i == 0)
      uf.unionBySize(hashed, 0);
  }

  private int hash(int i, int j) {
    return i * n + j + 1;
  }
}