Hard

Number of Ways to Build Sturdy Brick Wall

LAB

Return the number of sturdy walls of height h and width w using bricks of given widths, modulo 1000000007. Adjacent rows cannot share internal seams.

EXAMPLES

Example 1

Input
{
  "height": 2,
  "width": 3,
  "bricks": [
    1,
    2
  ]
}

Output
2

FUNCTION SHAPE

height: intwidth: intbricks: intArray→int

SOLUTION NOTE

Track brick edges as bitmask. Current row edges can't align with previous row edges. Don't mark final edge at width.

Reveal reference solution +

pythonREFERENCE

def buildWall(self, height: int, width: int, bricks: List[int]) -> int:
    MOD = 10**9 + 7

    @cache
    def dp(i, j, curr_mask, prev_mask):
        if i == height: return 1
        if j == width: return dp(i + 1, 0, 0, curr_mask)

        res = 0
        for b in bricks:
            if j + b <= width and (prev_mask & (1 << (j + b))) == 0:
                new_mask = curr_mask | (1 << (j + b)) if j + b < width else curr_mask
                res = (res + dp(i, j + b, new_mask, prev_mask)) % MOD
        return res

    return dp(0, 0, 0, 0)

TimeO(height × width × 2^width × bricks)

SpaceO(height × width × 4^width)

Open on LeetCode ↗