Problem Description

You need to build a brick wall with specific dimensions: height rows and width units wide. You have an infinite supply of different types of bricks, where each brick type has a height of 1 unit and a width specified in the bricks array. For example, if bricks = [1, 2, 3], you can use bricks of width 1, 2, or 3 units.

The key constraints are:

1. Each row must be exactly width units long
2. Bricks cannot be rotated (they always have height 1)
3. The wall must be "sturdy" - this means that vertical joints between bricks in adjacent rows should not align (except at the ends of the wall)

For example, if you have two adjacent rows:

• Row 1: [brick of width 2][brick of width 3] (total width = 5)
• Row 2: [brick of width 3][brick of width 2] (total width = 5)

These rows would NOT be sturdy because there's a vertical joint at position 2 in row 1 and position 3 in row 2 that don't align, which is good. But if row 2 was [brick of width 2][brick of width 3], the joints would align at position 2, making it not sturdy.

The problem asks you to count the total number of different ways to build a sturdy wall of the given dimensions. Since this number can be very large, return the answer modulo 10^9 + 7.

The solution approach involves:

1. Finding all possible ways to fill a single row of width width using the available bricks
2. Determining which row configurations can be placed adjacent to each other (checking if joints align)
3. Using dynamic programming to count the number of ways to build the entire wall of height height

Intuition

The first insight is to recognize that this is a dynamic programming problem with a twist - we need to track compatibility between consecutive rows.

Think about building the wall row by row from bottom to top. For each row, we need to know all possible ways to arrange bricks to get exactly width units. This is a classic backtracking problem - we try placing each brick type and recursively fill the remaining width until we reach exactly width units.

Once we have all possible row configurations, the next challenge is determining which rows can be placed on top of each other. Two rows are compatible if their internal joints (excluding the ends at position 0 and width) don't align. To check this, we can compare the cumulative positions where joints occur in each row. If we track the positions where bricks end in each row (except the last position), two rows are incompatible if they share any of these positions.

For example, if row A has bricks [2, 3] for width 5, joints are at position 2. If row B has bricks [3, 2], joints are at position 3. These rows are compatible because positions 2 and 3 don't overlap.

Now comes the dynamic programming insight: Let dp[i][j] represent the number of ways to build a wall of height i+1 where the top row uses configuration j. For the first row (base case), each configuration can be used once, so dp[0][j] = 1 for all valid configurations.

For each subsequent row i, we can place configuration j on top only if it's compatible with the configuration used in the previous row. So dp[i][j] equals the sum of dp[i-1][k] for all configurations k that are compatible with j.

By precomputing a compatibility graph where each node represents a row configuration and edges connect compatible configurations, we can efficiently calculate the DP transitions. The final answer is the sum of all dp[height-1][j] values, representing all possible ways to build the complete wall.

Learn more about Dynamic Programming and Bitmask patterns.

Solution Approach

The implementation consists of three main parts: generating row configurations, building a compatibility graph, and dynamic programming to count valid walls.

Step 1: Generate All Valid Row Configurations

The dfs function uses backtracking to find all ways to fill a row of width width:

def dfs(v):
    if v > width:
        return
    if v == width:
        s.append(t[:])
        return
    for x in bricks:
        t.append(x)
        dfs(v + x)
        t.pop()

• v tracks the current width filled
• t is a temporary list storing the current brick arrangement
• When v == width, we found a valid configuration and add it to s
• We try each brick type and recursively fill the remaining width

Step 2: Build Compatibility Graph

The check function determines if two row configurations can be adjacent:

def check(a, b):
    s1, s2 = a[0], b[0]
    i = j = 1
    while i < len(a) and j < len(b):
        if s1 == s2:
            return False
        if s1 < s2:
            s1 += a[i]
            i += 1
        else:
            s2 += b[j]
            j += 1
    return True

• It uses two pointers to track cumulative positions of joints in both rows
• s1 and s2 represent the current cumulative width in each row
• If s1 == s2 at any point (except at 0 and width), the joints align and rows are incompatible
• The function returns True if no internal joints align

A graph g is built where g[i] contains all row configurations compatible with configuration i:

for i in range(n):
    if check(s[i], s[i]):
        g[i].append(i)
    for j in range(i + 1, n):
        if check(s[i], s[j]):
            g[i].append(j)
            g[j].append(i)

Step 3: Dynamic Programming

The DP table dp[i][j] represents the number of ways to build a wall of height i+1 with configuration j on top:

dp = [[0] * n for _ in range(height)]
for j in range(n):
    dp[0][j] = 1  # Base case: first row

for i in range(1, height):
    for j in range(n):
        for k in g[j]:
            dp[i][j] += dp[i - 1][k]
            dp[i][j] %= mod

• Initialize first row: each configuration can be used once
• For each subsequent row, sum the ways from all compatible previous configurations
• Apply modulo operation to prevent overflow

The final answer is sum(dp[-1]) % mod, which sums all possible ways to build a wall of the full height with any valid top configuration.

The time complexity is O(height × n²) where n is the number of valid row configurations, and space complexity is O(height × n) for the DP table.

Example Walkthrough

Let's walk through a small example with height = 2, width = 5, and bricks = [1, 2, 3].

Step 1: Find all valid row configurations

Using backtracking, we find all ways to fill width 5:

• Starting with empty row, we try each brick:
  • Place brick of width 1: remaining width = 4
    • Place another 1: remaining = 3
      • Place 3: total = 5 ✓ → Configuration: [1, 1, 3]
    • Place 2: remaining = 2
      • Place 2: total = 5 ✓ → Configuration: [1, 2, 2]
  • Place brick of width 2: remaining width = 3
    • Place 3: total = 5 ✓ → Configuration: [2, 3]
  • Place brick of width 3: remaining width = 2
    • Place 2: total = 5 ✓ → Configuration: [3, 2]

Valid configurations found:

• Config 0: [1, 1, 3] (joints at positions 1, 2)
• Config 1: [1, 2, 2] (joints at positions 1, 3)
• Config 2: [2, 3] (joint at position 2)
• Config 3: [3, 2] (joint at position 3)

Step 2: Build compatibility graph

Check which configurations can be placed adjacent to each other:

• Config 0 [1, 1, 3] vs Config 0 [1, 1, 3]: Joints align at positions 1 and 2 → Incompatible
• Config 0 [1, 1, 3] vs Config 1 [1, 2, 2]: Joints align at position 1 → Incompatible
• Config 0 [1, 1, 3] vs Config 2 [2, 3]: Joints align at position 2 → Incompatible
• Config 0 [1, 1, 3] vs Config 3 [3, 2]: No joints align → Compatible
• Config 1 [1, 2, 2] vs Config 1 [1, 2, 2]: Joints align at positions 1 and 3 → Incompatible
• Config 1 [1, 2, 2] vs Config 2 [2, 3]: No joints align → Compatible
• Config 1 [1, 2, 2] vs Config 3 [3, 2]: Joints align at position 3 → Incompatible
• Config 2 [2, 3] vs Config 2 [2, 3]: Joint aligns at position 2 → Incompatible
• Config 2 [2, 3] vs Config 3 [3, 2]: No joints align → Compatible
• Config 3 [3, 2] vs Config 3 [3, 2]: Joint aligns at position 3 → Incompatible

Compatibility graph:

• Config 0 → [3]
• Config 1 → [2]
• Config 2 → [1, 3]
• Config 3 → [0, 2]

Step 3: Dynamic Programming

Build DP table for height 2:

Initial state (row 0):

• dp[0][0] = 1 (Config 0 on bottom)
• dp[0][1] = 1 (Config 1 on bottom)
• dp[0][2] = 1 (Config 2 on bottom)
• dp[0][3] = 1 (Config 3 on bottom)

Calculate row 1:

• dp[1][0]: Config 0 on top, compatible with Config 3 from row 0
  • dp[1][0] = dp[0][3] = 1
• dp[1][1]: Config 1 on top, compatible with Config 2 from row 0
  • dp[1][1] = dp[0][2] = 1
• dp[1][2]: Config 2 on top, compatible with Configs 1 and 3 from row 0
  • dp[1][2] = dp[0][1] + dp[0][3] = 1 + 1 = 2
• dp[1][3]: Config 3 on top, compatible with Configs 0 and 2 from row 0
  • dp[1][3] = dp[0][0] + dp[0][2] = 1 + 1 = 2

Final Answer: sum(dp[1]) = 1 + 1 + 2 + 2 = 6

There are 6 different ways to build a sturdy wall of height 2 and width 5 with the given bricks.

Solution Implementation

Time and Space Complexity

Time Complexity: O(2^width * n^2 + height * n^2) where n is the number of valid row configurations.

• The dfs function explores all possible ways to fill a row with bricks. In the worst case, using bricks of size 1, this creates 2^width recursive calls (at each position, we can either place a brick or not).
• After generating all valid row configurations, there are n such configurations where n ≤ 2^width.
• The check function runs in O(width) time to verify if two rows are compatible (no aligned cracks).
• Building the adjacency graph requires O(n^2) comparisons, each taking O(width) time, resulting in O(n^2 * width).
• The dynamic programming phase iterates through height rows, and for each of the n configurations, it checks all adjacent configurations, resulting in O(height * n^2) operations.
• Overall: O(2^width + n^2 * width + height * n^2) ≈ O(2^width * n^2 + height * n^2)

Space Complexity: O(n * width + n^2 + height * n)

• The s list stores all valid row configurations, with each configuration having at most width elements: O(n * width).
• The adjacency graph g stores edges between compatible rows: O(n^2) in the worst case.
• The DP table dp has dimensions height × n: O(height * n).
• The recursion stack depth for dfs is at most width: O(width).
• Overall: O(n * width + n^2 + height * n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Handling Self-Compatibility Check

The Pitfall: A critical oversight is forgetting to check if a row pattern can be placed adjacent to itself. Many developers assume they only need to check compatibility between different patterns, leading to incorrect results when the same pattern appears in consecutive rows.

Why It Happens: The nested loop that builds the compatibility graph typically compares pattern i with patterns j where j > i. This misses the case where pattern i needs to be checked against itself.

Incorrect Implementation:

# WRONG: Missing self-compatibility check
for i in range(num_patterns):
    for j in range(i + 1, num_patterns):  # Only checks different patterns
        if are_rows_compatible(all_row_patterns[i], all_row_patterns[j]):
            compatibility_graph[i].append(j)
            compatibility_graph[j].append(i)

Correct Implementation:

# CORRECT: Includes self-compatibility check
for i in range(num_patterns):
    # Check if pattern can be adjacent to itself
    if are_rows_compatible(all_row_patterns[i], all_row_patterns[i]):
        compatibility_graph[i].append(i)

    # Check compatibility with other patterns
    for j in range(i + 1, num_patterns):
        if are_rows_compatible(all_row_patterns[i], all_row_patterns[j]):
            compatibility_graph[i].append(j)
            compatibility_graph[j].append(i)

Example Where This Matters: Consider width = 4 and bricks = [1, 2]:

• Pattern [1, 1, 2] has joints at positions 1, 2, and 4
• When placed adjacent to itself, joints at positions 1 and 2 align perfectly
• This pattern is NOT self-compatible and shouldn't be allowed in consecutive rows

2. Overflow Due to Missing Modulo Operations

The Pitfall: Forgetting to apply the modulo operation during intermediate calculations can cause integer overflow, especially when the wall height is large.

Incorrect Implementation:

# WRONG: Missing modulo in the inner loop
for row in range(1, height):
    for current_pattern in range(num_patterns):
        for compatible_pattern in compatibility_graph[current_pattern]:
            dp[row][current_pattern] += dp[row - 1][compatible_pattern]
        # Modulo applied too late - overflow may have already occurred
        dp[row][current_pattern] %= MOD

Correct Implementation:

# CORRECT: Apply modulo after each addition
for row in range(1, height):
    for current_pattern in range(num_patterns):
        for compatible_pattern in compatibility_graph[current_pattern]:
            dp[row][current_pattern] += dp[row - 1][compatible_pattern]
            dp[row][current_pattern] %= MOD  # Apply immediately to prevent overflow

3. Misunderstanding Joint Alignment Logic

The Pitfall: The compatibility check function can be tricky to implement correctly. A common mistake is comparing the wrong values or incorrectly handling the pointers.

Incorrect Implementation:

# WRONG: Comparing indices instead of cumulative positions
def are_rows_compatible(row_a, row_b):
    idx_a, idx_b = 0, 0
    while idx_a < len(row_a) - 1 and idx_b < len(row_b) - 1:
        if idx_a == idx_b:  # Wrong: comparing indices not positions
            return False
        if row_a[idx_a] < row_b[idx_b]:
            idx_a += 1
        else:
            idx_b += 1
    return True

Correct Implementation:

# CORRECT: Comparing cumulative positions of joints
def are_rows_compatible(row_a, row_b):
    sum_a, sum_b = row_a[0], row_b[0]
    idx_a, idx_b = 1, 1

    while idx_a < len(row_a) and idx_b < len(row_b):
        if sum_a == sum_b:  # Correct: comparing cumulative positions
            return False
        if sum_a < sum_b:
            sum_a += row_a[idx_a]
            idx_a += 1
        else:
            sum_b += row_b[idx_b]
            idx_b += 1
    return True

Why This Matters: Joint positions are determined by the cumulative sum of brick widths, not by the index in the array. For example, [2, 3] has a joint at position 2, while [1, 1, 3] has joints at positions 1 and 2.