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

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

✓ Brute Force (Generate All Combinations)

⏱️ Time: O(k^height) Space: O(height * width)

This approach generates all possible ways to fill each row with the given bricks, then checks if the resulting wall satisfies the sturdy constraint by ensuring no internal joints align between adjacent rows.

Dynamic Programming with Memoization (Optimal)

⏱️ Time: O(P^2 * H) Space: O(P * H)

This optimal approach first generates all possible row patterns represented as bitmasks of joint positions. Then uses dynamic programming with memoization to efficiently count the number of ways to build valid walls by tracking which patterns can follow each other.

Brute Force (Generate All Combinations) — Algorithm Steps

Generate all possible ways to fill a single row of width W using given bricks
For each row arrangement, calculate the positions of internal joints
Use recursion to build the wall row by row
For each new row, check if its joints conflict with the previous row
Count all valid complete walls

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Row Patterns

Find all ways to fill width=4 with bricks [1,2]

Check Joint Conflicts

Verify adjacent rows don't share internal joint positions

Build Wall Recursively

Try each valid pattern for the next row

Code -

solution.c — C

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

#define MOD 1000000007
#define MAX_ROWS 201
#define MAX_PATTERNS 50000

int height, width;
int bricks[10];
int brickCount;

// Store all valid row patterns as bitmasks
// Bit i set means there's a joint AFTER position i (i=1..width-1)
int patterns[MAX_PATTERNS];
int patternCount = 0;

// Generate all valid row patterns using recursion
// pos = current position filled, mask = joints so far
void generatePatterns(int pos, int mask) {
    if (pos == width) {
        patterns[patternCount++] = mask;
        return;
    }
    for (int i = 0; i < brickCount; i++) {
        int newPos = pos + bricks[i];
        if (newPos <= width) {
            int newMask = mask;
            // If not at the end, mark joint at newPos
            if (newPos < width) {
                newMask |= (1 << newPos);
            }
            generatePatterns(newPos, newMask);
        }
    }
}

// Check if two patterns are compatible (no shared joints)
int compatible(int mask1, int mask2) {
    return (mask1 & mask2) == 0;
}

int solution() {
    // Step 1: Generate all valid row patterns
    patternCount = 0;
    generatePatterns(0, 0);

    if (patternCount == 0) return 0;

    // Step 2: Brute force - try all combinations of patterns for each row
    // dp[i] = number of ways to build walls ending with pattern i
    long long* dp     = (long long*)calloc(patternCount, sizeof(long long));
    long long* newdp  = (long long*)calloc(patternCount, sizeof(long long));

    // First row: all patterns are valid
    for (int i = 0; i < patternCount; i++) {
        dp[i] = 1;
    }

    // For each subsequent row, try all combinations
    for (int row = 1; row < height; row++) {
        memset(newdp, 0, patternCount * sizeof(long long));

        // Try every combination of previous pattern + current pattern
        for (int prev = 0; prev < patternCount; prev++) {
            if (dp[prev] == 0) continue;
            for (int curr = 0; curr < patternCount; curr++) {
                if (compatible(patterns[prev], patterns[curr])) {
                    newdp[curr] = (newdp[curr] + dp[prev]) % MOD;
                }
            }
        }

        // Swap dp and newdp
        long long* tmp = dp;
        dp = newdp;
        newdp = tmp;
    }

    // Sum all ways
    long long result = 0;
    for (int i = 0; i < patternCount; i++) {
        result = (result + dp[i]) % MOD;
    }

    free(dp);
    free(newdp);
    return (int)result;
}

void parseBricks(const char* line) {
    brickCount = 0;
    const char* p = line;
    while (*p) {
        while (*p && (*p < '0' || *p > '9')) p++;
        if (!*p) break;
        int num = 0;
        while (*p >= '0' && *p <= '9') num = num * 10 + (*p++ - '0');
        bricks[brickCount++] = num;
    }
}

int main() {
    static char line[1024 * 1024];
    int totalLen = 0;
    int c;
    while ((c = getchar()) != EOF && totalLen < (int)sizeof(line) - 1)
        line[totalLen++] = (char)c;
    line[totalLen] = '\0';

    // Parse tokens: height, width, bricks array
    char heightLine[32] = {0}, widthLine[32] = {0}, bricksLine[256] = {0};
    char* p = line;

    while (*p) {
        while (*p == '\n' || *p == '\r' || *p == ' ') p++;
        if (!*p) break;
        char* start = p;
        while (*p && *p != '\n' && *p != '\r') p++;
        int len = (int)(p - start);
        char token[256] = {0};
        if (len >= 256) len = 255;
        strncpy(token, start, len);
        token[len] = '\0';

        if (strchr(token, '[') != NULL)
            strncpy(bricksLine, token, 255);
        else if (strlen(heightLine) == 0)
            strncpy(heightLine, token, 31);
        else if (strlen(widthLine) == 0)
            strncpy(widthLine, token, 31);
    }

    height = atoi(heightLine);
    width  = atoi(widthLine);
    parseBricks(bricksLine);

    printf("%d\n", solution());
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k^height)

Where k is the number of ways to fill one row. In worst case, this can be exponential

✓ Linear Growth

Space Complexity

O(height * width)

Recursion stack depth times the space needed to store row configurations

✓ 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

Number of Ways to Build Sturdy Brick Wall - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force (Generate All Combinations) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler