LeetCode 2184 - Number of Ways to Build Sturdy Brick Wall

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Bit Manipulation, Bitmask

Solution

Problem Understanding

The problem asks us to compute the number of ways to build a wall of given height and width using bricks of specified widths, such that the wall is sturdy. A wall is sturdy if no two adjacent rows have bricks that meet at the same position horizontally, except at the ends of the wall.

The inputs are:

height - the number of rows in the wall.
width - the total horizontal length of each row.
bricks - an array of unique integers, each representing a brick width. Bricks have a height of 1, cannot be rotated, and are available in unlimited supply.

The output is the total number of distinct ways to build a sturdy wall, modulo $10^9 + 7$.

Constraints indicate that the maximum width is small (≤10), the number of brick types is small (≤10), and the height can be up to 100. This suggests a solution that can precompute possible rows and combine them efficiently, rather than brute-forcing all wall configurations.

Important edge cases include:

width smaller than all brick types - no rows can be formed.
Single-row walls - no sturdiness constraints.
Bricks that exactly fit the width versus bricks that do not.

Approaches

The brute-force approach would be to generate all possible rows of length width using the available bricks, then recursively stack rows while checking the sturdiness condition at each step. This method is correct but exponentially slow, especially as height increases, because each row can be combined with multiple previous rows recursively.

The optimal approach uses bitmasking and dynamic programming. The key observation is that the position of cracks between bricks in a row determines whether two rows can be stacked sturdily. By encoding the cracks as a bitmask for each row configuration, we can precompute which rows are compatible. Then we use dynamic programming across the height of the wall to count valid combinations efficiently.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((#row_configs)^height)	O(#row_configs * height)	Recursively stack all rows, check sturdiness each time
Optimal	O(#row_configs^2 * height)	O(#row_configs^2 + height)	Precompute row masks and DP table, multiply compatible rows

Algorithm Walkthrough

Generate all valid rows: Recursively create all sequences of bricks that sum to width. For each row, record the positions of cracks (where bricks meet, excluding ends). Each crack set can be encoded as a bitmask for fast comparison.
Precompute compatibility: For each pair of rows, check if the cracks do not overlap (except at ends). Store compatible rows in a dictionary or adjacency list.
Dynamic programming initialization: Create a DP array dp[r] representing the number of ways to build a wall of height h ending with row configuration r. Initialize with dp[row] = 1 for all rows (first row).
Build the wall row by row: For each row from 2 to height, update a new DP array by summing over all compatible previous rows for each current row.
Sum the results: After reaching the top row, sum the counts across all row configurations. Return modulo $10^9 + 7$.

Why it works: The algorithm guarantees correctness because it enumerates all possible row sequences and uses DP to propagate valid combinations, only stacking rows when the sturdiness constraint is satisfied.

Python Solution

from typing import List

class Solution:
    MOD = 10**9 + 7
    
    def buildWall(self, height: int, width: int, bricks: List[int]) -> int:
        # Step 1: Generate all valid row configurations as crack bitmasks
        row_masks = []

        def dfs(pos, mask):
            if pos == width:
                row_masks.append(mask)
                return
            for b in bricks:
                if pos + b <= width:
                    new_mask = mask
                    if pos + b < width:  # add crack if not at the end
                        new_mask |= 1 << (pos + b - 1)
                    dfs(pos + b, new_mask)
        
        dfs(0, 0)
        
        # Step 2: Precompute compatible rows
        compatible = {mask: [] for mask in row_masks}
        for mask1 in row_masks:
            for mask2 in row_masks:
                if mask1 & mask2 == 0:  # no overlapping cracks
                    compatible[mask1].append(mask2)
        
        # Step 3: Dynamic programming across height
        dp = {mask: 1 for mask in row_masks}  # first row
        for _ in range(1, height):
            new_dp = {mask: 0 for mask in row_masks}
            for mask in row_masks:
                for prev in compatible[mask]:
                    new_dp[mask] = (new_dp[mask] + dp[prev]) % self.MOD
            dp = new_dp
        
        # Step 4: Sum all configurations
        return sum(dp.values()) % self.MOD

The code first enumerates all valid row configurations recursively. Each row's cracks are encoded in a bitmask, which allows constant-time compatibility checks using bitwise AND. Then, dynamic programming aggregates the number of ways to build the wall row by row. Modulo is applied at each step to prevent overflow.

Go Solution

func buildWall(height int, width int, bricks []int) int {
    const MOD = 1_000_000_007
    type void struct{}
    var masks []int

    var dfs func(pos int, mask int)
    dfs = func(pos int, mask int) {
        if pos == width {
            masks = append(masks, mask)
            return
        }
        for _, b := range bricks {
            if pos+b <= width {
                newMask := mask
                if pos+b < width {
                    newMask |= 1 << (pos + b - 1)
                }
                dfs(pos+b, newMask)
            }
        }
    }
    dfs(0, 0)

    // Precompute compatibility
    compatible := make(map[int][]int)
    for _, m1 := range masks {
        compatible[m1] = []int{}
        for _, m2 := range masks {
            if m1&m2 == 0 {
                compatible[m1] = append(compatible[m1], m2)
            }
        }
    }

    // DP
    dp := make(map[int]int)
    for _, m := range masks {
        dp[m] = 1
    }

    for h := 1; h < height; h++ {
        newDP := make(map[int]int)
        for _, m := range masks {
            sum := 0
            for _, prev := range compatible[m] {
                sum = (sum + dp[prev]) % MOD
            }
            newDP[m] = sum
        }
        dp = newDP
    }

    res := 0
    for _, val := range dp {
        res = (res + val) % MOD
    }
    return res
}

Go handles maps and bitwise operations similarly to Python. The DFS uses recursion to generate row masks. Compatibility is stored in a map, and DP is implemented as a map to aggregate row counts. Modulo is applied during aggregation.

Worked Examples

Example 1: height = 2, width = 3, bricks = [1,2]

Possible rows: [1,1,1], [1,2], [2,1]
Corresponding crack masks: 0b011 (3), 0b01 (1), 0b10 (2)
Compatible rows for stacking:
0b01 compatible with 0b10
0b10 compatible with 0b01
0b11 compatible with none
DP step 1: {1:1, 2:1, 3:1}
DP step 2: update using compatible: {1:1, 2:1, 3:0}
Sum = 2

Example 2: height = 1, width = 1, bricks = [5]

No rows can be formed → 0 ways

Complexity Analysis

Measure	Complexity	Explanation
Time	O(H * R^2)	H = height, R = number of valid row masks. Precompute compatible rows and DP multiplication
Space	O(R^2 + R)	Store compatible rows (O(R^2)) and DP array (O(R))

The number of row configurations R is small due to width ≤10 and bricks ≤10. This ensures feasibility.

Test Cases

# Provided examples
assert Solution().buildWall(2, 3, [1,2]) == 2  # basic 2-row sturdy wall
assert Solution().buildWall(1, 1, [5]) == 0    # brick too wide

# Edge cases
assert Solution().buildWall(1, 1, [1]) == 1    # single brick fits exactly
assert Solution().buildWall(3, 3, [1,2]) == 4  # small 3