Number of Ways to Build Sturdy Brick Wall

Number of Ways to Build Sturdy Brick Wall - Problem

You're tasked with building a sturdy brick wall with specific dimensions and constraints. Given a wall of height rows and width units, you must construct it using bricks from an array where each brick has height 1 and width bricks[i].

Key Requirements:

Each row must be exactly width units long
You have an infinite supply of each brick type
Bricks cannot be rotated
Sturdy constraint: Adjacent rows cannot have joints at the same position (except at the wall ends)

Return the number of ways to build such a wall, modulo 10⁹ + 7.

Example: With height=2, width=3, bricks=[1,2], you could have row 1 as [2,1] and row 2 as [1,2], since their internal joints don't align.

Input & Output

example_1.py — Basic Case

$ Input: height = 2, width = 3, bricks = [1, 2]

› Output: 2

💡 Note: Two valid ways: Row1=[2,1] Row2=[1,2], and Row1=[1,2] Row2=[2,1]. In both cases, internal joints don't align.

example_2.py — Single Row

$ Input: height = 1, width = 4, bricks = [1, 2]

› Output: 5

💡 Note: One row can be filled as: [1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2]. All are valid since there's no adjacent row to conflict with.

example_3.py — No Valid Arrangement

$ Input: height = 2, width = 3, bricks = [2]

› Output: 0

💡 Note: Width 3 cannot be filled using only bricks of size 2 (3 is odd, but we need even sum). No valid arrangements exist.

Constraints

1 ≤ height ≤ 200
1 ≤ width ≤ 200
1 ≤ bricks.length ≤ 10
1 ≤ bricks[i] ≤ width
All bricks[i] are unique
Answer fits in 32-bit integer after modulo 10⁹ + 7

Visualization

Tap to expand

Understanding the Visualization

Generate Row Patterns

Find all possible ways to fill one row with given bricks, recording internal joint positions

Pattern Compatibility

Create a matrix showing which row patterns can be placed adjacent to each other

Dynamic Programming

Use DP to count ways to build the wall, ensuring each row uses only compatible patterns

Sum All Possibilities

The final answer is the sum of all valid ways to complete the wall

Key Takeaway

🎯 Key Insight: The problem becomes manageable when we realize we only need to track joint positions (using bitmasks) rather than actual brick arrangements, and use dynamic programming to efficiently count valid wall configurations.

Asked in

G Google 45 a Amazon 38 f Meta 32 ⊞ Microsoft 28

This problem requires dynamic programming with bitmask optimization. The key insight is to represent joint positions as bitmasks and use DP to count valid wall configurations. First generate all possible row patterns, then build a compatibility matrix to check which patterns can be adjacent (no overlapping internal joints). Finally, use DP where dp[row][pattern] represents the number of ways to reach a specific pattern at each row level. The optimal solution runs in O(P² × H) time where P is the number of unique row patterns.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Memoization (Optimal)	O(P^2 * H)	O(P * H)	Use bitmasks to represent joint patterns and DP to count valid combinations
Brute Force (Generate All Combinations)	O(k^height)	O(height * width)	Generate all possible row arrangements and check validity

Dynamic Programming with Memoization (Optimal) — Algorithm Steps

Generate all valid row patterns and represent joint positions as bitmasks
Create compatibility matrix between patterns (no shared internal joints)
Use DP where dp[row][pattern] = ways to reach this row with this pattern
For each row, sum ways from all compatible patterns in previous row
Return sum of all patterns in the final row

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Bitmask Patterns

Convert joint positions to binary representation

Build Compatibility Matrix

Check which patterns can be adjacent (no overlapping bits)

DP Transition

Count ways to reach each pattern at each row level

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MOD 1000000007
#define MAX_PATTERNS 1000

int patterns[MAX_PATTERNS];
int patternCount = 0;
bool patternExists[1 << 20] = {false};

void generateHelper(int remaining, int currentPos, int jointsMask, int width, int* bricks, int brickCount) {
    if (remaining == 0) {
        if (!patternExists[jointsMask]) {
            patterns[patternCount++] = jointsMask;
            patternExists[jointsMask] = true;
        }
        return;
    }
    
    for (int i = 0; i < brickCount; i++) {
        if (bricks[i] <= remaining) {
            int newPos = currentPos + bricks[i];
            int newMask = jointsMask;
            if (newPos < width) {
                newMask = jointsMask | (1 << newPos);
            }
            generateHelper(remaining - bricks[i], newPos, newMask, width, bricks, brickCount);
        }
    }
}

int numWaysToFormWall(int height, int width, int* bricks, int brickCount) {
    patternCount = 0;
    memset(patternExists, false, sizeof(patternExists));
    
    generateHelper(width, 0, 0, width, bricks, brickCount);
    
    // Build compatibility matrix
    bool compatible[MAX_PATTERNS][MAX_PATTERNS];
    for (int i = 0; i < patternCount; i++) {
        for (int j = 0; j < patternCount; j++) {
            compatible[i][j] = (patterns[i] & patterns[j]) == 0;
        }
    }
    
    // DP
    long long prevDp[MAX_PATTERNS];
    for (int i = 0; i < patternCount; i++) {
        prevDp[i] = 1;
    }
    
    for (int row = 1; row < height; row++) {
        long long currDp[MAX_PATTERNS] = {0};
        for (int currPattern = 0; currPattern < patternCount; currPattern++) {
            for (int prevPattern = 0; prevPattern < patternCount; prevPattern++) {
                if (compatible[prevPattern][currPattern]) {
                    currDp[currPattern] = (currDp[currPattern] + prevDp[prevPattern]) % MOD;
                }
            }
        }
        memcpy(prevDp, currDp, sizeof(currDp));
    }
    
    long long result = 0;
    for (int i = 0; i < patternCount; i++) {
        result = (result + prevDp[i]) % MOD;
    }
    return result;
}

int main() {
    int height, width;
    scanf("%d %d", &height, &width);
    
    int bricks[20], brickCount = 0;
    char line[1000];
    fgets(line, sizeof(line), stdin); // consume newline
    fgets(line, sizeof(line), stdin);
    
    char* token = strtok(line, " ");
    while (token != NULL) {
        bricks[brickCount++] = atoi(token);
        token = strtok(NULL, " ");
    }
    
    printf("%d\n", numWaysToFormWall(height, width, bricks));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(P^2 * H)

Where P is the number of unique row patterns and H is height. We check compatibility between all pattern pairs once, then DP through H rows

✓ Linear Growth

Space Complexity

O(P * H)

DP table storing ways to reach each pattern at each row level

✓ Linear Space

38.5K Views

Medium Frequency

~25 min Avg. Time

1.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Memoization (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler