Skip to content

2184. Number of Ways to Build Sturdy Brick Wall

  • Time: $O(n \cdot \texttt{height})$, where $n = |\texttt{rows}|$
  • Space: $O(n)$
 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
class Solution {
 public:
  int buildWall(int height, int width, vector<int>& bricks) {
    constexpr int kMod = 1'000'000'007;
    // Stores the valid rows in bitmask.
    vector<int> rows;
    buildRows(width, bricks, 0, rows);

    const int n = rows.size();
    // dp[i] := the number of ways to build `h` height walls with rows[i] in the
    // bottom
    vector<long> dp(n, 1);
    // graph[i] := the valid neighbors of rows[i]
    vector<vector<int>> graph(n);

    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        if (!(rows[i] & rows[j]))
          graph[i].push_back(j);

    for (int h = 2; h <= height; ++h) {
      vector<long> newDp(n);
      for (int i = 0; i < n; ++i)
        for (const int v : graph[i]) {
          newDp[i] += dp[v];
          newDp[i] %= kMod;
        }
      dp = std::move(newDp);
    }

    return accumulate(dp.begin(), dp.end(), 0L) % kMod;
  }

 private:
  void buildRows(int width, const vector<int>& bricks, int path,
                 vector<int>& rows) {
    for (const int brick : bricks)
      if (brick == width)
        rows.push_back(path);
      else if (brick < width) {
        const int newWidth = width - brick;
        buildRows(newWidth, bricks, path | 1 << newWidth, rows);
      }
  }
};

 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
class Solution {
  public int buildWall(int height, int width, int[] bricks) {
    final int kMod = 1_000_000_007;
    // Stores the valid rows in bitmask.
    List<Integer> rows = new ArrayList<>();
    buildRows(width, bricks, 0, rows);

    final int n = rows.size();
    // dp[i] := the number of ways to build `h` height walls With rows[i] in the bottom
    long[] dp = new long[n];
    // graph[i] := the valid neighbors of rows[i]
    List<Integer>[] graph = new List[n];

    Arrays.fill(dp, 1);

    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();

    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        if ((rows.get(i) & rows.get(j)) == 0)
          graph[i].add(j);

    for (int h = 2; h <= height; ++h) {
      long[] newDp = new long[n];
      for (int i = 0; i < n; ++i)
        for (final int v : graph[i]) {
          newDp[i] += dp[v];
          newDp[i] %= kMod;
        }
      dp = newDp;
    }

    return (int) (Arrays.stream(dp).sum() % kMod);
  }

  private void buildRows(int width, int[] bricks, int path, List<Integer> rows) {
    for (final int brick : bricks)
      if (brick == width)
        rows.add(path);
      else if (brick < width) {
        final int newWidth = width - brick;
        buildRows(newWidth, bricks, path | 1 << newWidth, rows);
      }
  }
}

 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
class Solution:
  def buildWall(self, height: int, width: int, bricks: list[int]) -> int:
    kMod = 1_000_000_007
    # Stores the valid rows in bitmask.
    rows = []
    self._buildRows(width, bricks, 0, rows)

    n = len(rows)
    # dp[i] := the number of ways to build `h` height walls with rows[i] in the bottom
    dp = [1] * n
    # graph[i] := the valid neighbors of rows[i]
    graph = [[] for _ in range(n)]

    for i, a in enumerate(rows):
      for j, b in enumerate(rows):
        if not a & b:
          graph[i].append(j)

    for _ in range(2, height + 1):
      newDp = [0] * n
      for i in range(n):
        for v in graph[i]:
          newDp[i] += dp[v]
          newDp[i] %= kMod
      dp = newDp

    return sum(dp) % kMod

  def _buildRows(
      self,
      width: int,
      bricks: list[int],
      path: int,
      rows: list[int],
  ):
    for brick in bricks:
      if brick == width:
        rows.append(path)
      elif brick < width:
        newWidth = width - brick
        self._buildRows(newWidth, bricks, path | 2 << newWidth, rows)