Coding

Number of Ways to Build Sturdy Brick Wall

Asked at

Amazon

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

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]. 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****9 **+ 7.

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.

**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.

Consider a wall with height = 2, width = 4, and bricks =** [1, 2, 3]**. What is the number of ways to build a sturdy wall?

1 <= height <= 100
1 <= width <= 10
1 <= bricks.length <= 10
1 <=** bricks[i]** <= 10
All the values of bricks are unique.

cpp

class Solution {
public:
    int buildWall(int height, int width, vector<int>& bricks) {
        // Your code goes here
    }
};

java

class Solution {
    public int buildWall(int height, int width, int[] bricks) {
        // Your code goes here
    }
}

python

class Solution:
    def buildWall(self, height, width, bricks):
        # Your code goes here

javascript

class Solution {
    buildWall(height, width, bricks) {
        // Your code goes here
    }
}

csharp

public class Solution
{
    public int BuildWall(int height, int width, List<int> bricks)
    {
        // Your code goes here
    }
}

func buildWall(height, width int, bricks []int) int {
	// Your code goes here
}

Stuck? Show a way to structure it+

01Generate every row composition of the width.
02Encode its internal seams as a bitmask.
03Precompute pairs whose seam masks do not overlap.
04DP over height and last row pattern.
05Sum final states modulo MOD.

Reference answer

Because width is small, generate every possible row by backtracking over brick widths until the total equals width. Encode the internal joints of a row in a bitmask; do not include the two wall edges. Two adjacent rows are compatible exactly when (maskA & maskB) == 0, since a common internal seam makes the wall unstable. Precompute compatibility among all generated patterns, then let dp[row] count walls ending with each pattern. Initialize every pattern to one for height one and repeatedly transition only from compatible previous patterns, taking values modulo 1e9+7. If P is the number of row patterns, the straightforward runtime is O(height * P^2) and space O(P). This is far safer than trying to construct full walls directly.

Then expect these follow-ups

How can matrix exponentiation help for huge height?
Tests: linear recurrences
How would you list one valid wall?
Tests: parent tracking

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question