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.

Description Hints 3 Solution Video 28:18

2184. Number of Ways to Build Sturdy Brick Wall

Medium49.2% acceptance2 companiesPremium elsewhere, free here

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 i^th 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 10⁹ + 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.

Asked at 2 companies

MicroStrategy

Google

Topics

Hints open one at a time

Hint 1

A row of bricks can be represented uniquely by the points where two bricks are joined together.

Hint 2

For a given row of bricks, how many configurations of bricks could you have put below this row such that the wall is sturdy?

Hint 3

Use dynamic programming to store the number of possible sturdy walls with a given height and configuration of bricks on the top row.

28:18

Still stuck?Read the written solution, or watch a walkthrough.

Open solution