How hard is LeetCode 2184. Number of Ways to Build Sturdy Brick Wall?

LeetCode 2184. Number of Ways to Build Sturdy Brick Wall is rated Medium on LeetCode.

What topics does LeetCode 2184. Number of Ways to Build Sturdy Brick Wall cover?

LeetCode 2184. Number of Ways to Build Sturdy Brick Wall is tagged Bit Manipulation, Array, Dynamic Programming and Bitmask on LeetCode.

Is LeetCode 2184. Number of Ways to Build Sturdy Brick Wall a premium problem?

Yes. LeetCode 2184. Number of Ways to Build Sturdy Brick Wall is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Number of Ways to Build Sturdy Brick Wall — LeetCode 2184 Python Solution

MediumLeetCode PremiumBit ManipulationArrayDynamic ProgrammingBitmask

Problem: #2184
Pattern: Bit Manipulation
Reading time: 9 min
Source: leetcode.com

The problem

You are given integers height and width which specify the dimensions of a brick wall you are building. You are also given a 0-indexed array of unique integers bricks, where the ith brick has a height of 1 and a width of bricks[i].

Example

Input: height = 2, width = 3, bricks = [1,2]
Output: 2
Explanation: The first two walls in the diagram show the only two ways to build a sturdy brick wall.

Python solution

Python

class Solution:
    def buildWall(self, height: int, width: int, bricks: List[int]) -> int:
        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()

        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

        mod = 10**9 + 7
        s = []
        t = []
        dfs(0)
        g = defaultdict(list)
        n = len(s)
        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)
        dp = [[0] * n for _ in range(height)]
        for j in range(n):
            dp[0][j] = 1
        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
        return sum(dp[-1]) % mod

Complexity

Measure	Complexity
Time	O(n·m) (typical)
Space	O(n·m) or optimized auxiliary

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 2184. Number of Ways to Build Sturdy Brick Wall is filed here because LeetCode tags it Bit Manipulation and Bitmask, which is the vocabulary this hub collects.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2184. Number of Ways to Build Sturdy Brick Wall?: LeetCode 2184. Number of Ways to Build Sturdy Brick Wall is rated Medium on LeetCode.
What topics does LeetCode 2184. Number of Ways to Build Sturdy Brick Wall cover?: LeetCode 2184. Number of Ways to Build Sturdy Brick Wall is tagged Bit Manipulation, Array, Dynamic Programming and Bitmask on LeetCode.
Is LeetCode 2184. Number of Ways to Build Sturdy Brick Wall a premium problem?: Yes. LeetCode 2184. Number of Ways to Build Sturdy Brick Wall is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.