Skip to main content
Talentd

Number of Ways to Build Sturdy Brick Wall - Solution & Explanation

MediumPremiumFree on FleetCodeArrayDynamic ProgrammingBit ManipulationBitmask6 min readAsked at: MicroStrategy, Google
Practice this problem

Problem Statement

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 <= 100
  • 1 <= width <= 10
  • 1 <= bricks.length <= 10
  • 1 <= bricks[i] <= 10
  • All the values of bricks are unique.

Approach Overview

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.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Wall ConstructionExponentialExponentialOnly for conceptual understanding or extremely small inputs
Row State Bitmask + Dynamic ProgrammingO(S² * h)O(S * h)General optimal solution when width is small and row states can be enumerated

Video Solution

【每日一题】LeetCode 2184. Number of Ways to Build Sturdy Brick Wall • Huifeng Guan • 2,343 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Number of Ways to Build Sturdy Brick Wall easy or hard?
LeetCode classifies this problem as Medium difficulty. The challenge comes from modeling rows as bitmasks and combining them with dynamic programming across multiple levels of the wall.
Number of Ways to Build Sturdy Brick Wall Python/Java solution
Python and Java implementations typically follow the same pattern: generate row masks using DFS, precompute compatible state pairs, and run DP across the wall height. Bitwise AND operations are used to ensure seams do not align between adjacent rows.
How to solve Number of Ways to Build Sturdy Brick Wall in O(n)?
An O(n) solution is not typical for this problem because compatibility between row states must be checked. The standard approach enumerates all valid row masks and performs dynamic programming transitions between compatible rows. The resulting complexity is O(S^2 * h), which is efficient due to the small number of row states.
What is the best approach for Number of Ways to Build Sturdy Brick Wall?
The most efficient approach uses row state generation with bitmasks and dynamic programming. Each row configuration is encoded as a bitmask representing brick seam positions. Compatible rows are those where (mask1 & mask2) == 0. Dynamic programming stacks these row states across height h, giving a total complexity of O(S^2 * h) where S is the number of valid row states.
Is Number of Ways to Build Sturdy Brick Wall asked at Google/Amazon/Meta?
Problems combining state compression and dynamic programming, like this one, frequently appear in interviews at companies such as Google, Amazon, and Meta. Interviewers use them to test understanding of DP transitions, bitmask representations, and optimization of combinatorial states.
What data structure is used in Number of Ways to Build Sturdy Brick Wall?
The solution primarily uses arrays or lists to store row states and dynamic programming tables, along with integer bitmasks to represent seam positions. Bit manipulation allows constant-time compatibility checks between rows.
What is the time complexity of Number of Ways to Build Sturdy Brick Wall?
The optimal solution runs in O(S^2 * h) time. S represents the number of possible row configurations for the given width using the available brick sizes. For each height level, the algorithm transitions between compatible row states, resulting in the quadratic factor over S.

Ready to solve this problem?

Practice Number of Ways to Build Sturdy Brick Wall with our built-in code editor and test cases.

Practice on FleetCode
Previous

Brick Wall

Next

Bricks Falling When Hit