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]. You have an infinite supply of each type of brick and bricks may not be rotated.
Each row in the wall must be exactly width units long. For the wall to be sturdy, adjacent rows in the wall should not join bricks at the same location, except at the ends of the wall.
Return the number of ways to build a sturdy wall. Since the answer may be very large, return it modulo 109 + 7.
Example 1:
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. Note that the third wall in the diagram is not sturdy because adjacent rows join bricks 2 units from the left.
Example 2:
Input: height = 1, width = 1, bricks = [5] Output: 0 Explanation: There are no ways to build a sturdy wall because the only type of brick we have is longer than the width of the wall.
Constraints:
1 <= height <= 1001 <= width <= 101 <= bricks.length <= 101 <= bricks[i] <= 10bricks are unique.Problem Overview: You are building a wall with height h and width w using bricks of specific lengths. A wall is sturdy if vertical seams between bricks never align across adjacent rows. The task is to count how many valid walls can be built under these constraints.
Approach 1: Row State Enumeration + Dynamic Programming (Bitmask) (Time: O(S² * h), Space: O(S * h))
The core idea is to treat each row as a configuration of bricks whose seams can be represented with a bitmask. While building a row, every internal crack position (excluding the edges) becomes a bit set in the mask. Use DFS to generate all valid row configurations whose brick lengths sum to w. If the width is small (≤10 in constraints), the number of such states S remains manageable.
Two rows are compatible if their cracks do not align. With bitmasks, that check becomes a fast operation: (mask1 & mask2) == 0. If the result is zero, no seams overlap and the rows can be stacked safely. Precompute all compatible row pairs to avoid repeating this check during the DP transitions.
Once all row states are known, run dynamic programming across the wall height. Let dp[i][j] represent the number of ways to build the first i rows where the i-th row uses configuration j. For each row, iterate over all compatible configurations from the previous row and accumulate counts. The final answer is the sum of all configurations at height h.
This solution combines ideas from dynamic programming, bit manipulation, and efficient state compression. Bitmasks make seam alignment checks constant time and keep the state representation compact.
Recommended for interviews: Interviewers typically expect the row-state compression with DP. A brute-force search over all brick placements across the entire wall grows exponentially and becomes infeasible. Generating row states first, then stacking them with compatibility checks, demonstrates strong understanding of array iteration, bitmask modeling, and DP state transitions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Wall Construction | Exponential | Exponential | Only for conceptual understanding or extremely small inputs |
| Row State Bitmask + Dynamic Programming | O(S² * h) | O(S * h) | General optimal solution when width is small and row states can be enumerated |
【每日一题】LeetCode 2184. Number of Ways to Build Sturdy Brick Wall • Huifeng Guan • 2,335 views views
Watch 3 more video solutions →Practice Number of Ways to Build Sturdy Brick Wall with our built-in code editor and test cases.
Practice on FleetCode