2184. Number of Ways to Build Sturdy Brick Wall

Problem Description

The problem entails building a brick wall of specific dimensions, height and width, using bricks that come in different fixed widths (each brick is 1 unit high). In the array bricks, each brick's width is given, and we have an unlimited number of bricks of each size. The objective is to calculate the total number of ways to build the wall without aligning the joints of bricks from adjacent rows—except at the ends of the wall—to ensure the wall's sturdiness.

Each row must be exactly width units wide, and bricks may not be stacked atop each other; each brick spans the entire height of its row (which is 1 unit tall). The answer could be quite large, so we require the total count modulo 10^9 + 7.

Intuition

To solve this problem, we can think of each row in the wall as a sequence of bricks that fit perfectly within the given width. We start by finding all the valid sequences (arrangements) of bricks that will make a single row of the specified width. We represent these sequences as a list summed up to the width.

Once we have all the valid sequences for a single row, we approach the problem by assessing which sequences can sit above each other without their joints aligning. This links to the concept of graph theory, where we can think of each sequence as a node and edges that connect sequences that can be placed on top of each other (i.e., no aligned joints, except at the ends). With this graph, we can use dynamic programming to find all possible combinations of sequences for the total height of the wall.

We initialize a matrix of dynamic programming states where dp[i][j] represents the number of ways the wall can be built up to height i with the last row's configuration being the jth sequence. For each level of height, we compute the number of ways to continue building on top of each sequence, adding those from previous layers that are compatible (no aligning joints).

In the provided code, the recursive function dfs is used to generate all possible sequences that make up a row of width width. The check function verifies if two sequences can be placed one on top of the other without joints aligning. The nested for-loops iterate over the combinations of sequences to populate our graph g with valid sequences that can follow each other. In the final for-loops, we use dynamic programming to compute the number of possible configurations for each level of the wall until we reach the desired height, and return this count modulo 10^9 + 7 as the final answer.

Learn more about Dynamic Programming and Bitmask patterns.

Solution Approach

To implement the solution, we use several programming concepts such as recursion, depth-first search (DFS), dynamic programming, and graph theory. Here's how each part of the solution works:

• Depth-First Search (DFS): The dfs function is where we generate all the sequences of bricks that exactly fit the given width. We start with an empty sequence (t list) and extend it by adding bricks (x from bricks array) one by one. If adding a brick exceeds the width, we backtrack; this is the essence of DFS. When a sequence hits the exact width, we record it in the s list.

• Sequences Validation: To validate whether two sequences (rows of bricks) can be placed on top of each other, we create a check function. This function compares the cumulative width of bricks in two sequences to ensure that no joints (except at the ends) line up. As it iterates over the bricks, it maintains a running sum of widths (s1 and s2) for each sequence. If at any point the sums are equal (and not at the end), the sequences are incompatible.

• Graph Building: We construct a graph represented as a dictionary g, where each key is a sequence index, and its value is a list of indices of sequences that can be placed on top of the key sequence without joints aligning. This involves checking each sequence against every other valid sequence, facilitating the dynamic programming step.

• Dynamic Programming (DP): With the graph g in place, our next step is to count all viable ways to build the wall up to the specified height. We initialize a DP table dp, where dp[i][j] represents the number of ways to build the wall to height where the ith layer corresponds to the jth sequence from s. We start by setting dp[0][j] to 1 for all j, as there's exactly one way to start the wall with any sequence. Then for each subsequent layer (i), we add up the ways we can stack each sequence (j) on top of all the sequences (k) from the previous layer that are connected in graph g. We apply the modulo operation (mod) to keep the numbers within the required range.

• Summing Up Combinations: At the end, to get the total number of combinations, we iterate over the last layer of the dp table and sum up all the values, assessing the complete wall's height. This sum, modulo 10^9 + 7, gives us the final answer detailing the number of ways to construct the sturdy wall.

Throughout this process, we make use of:

• Recursion in the dfs function to explore all brick sequences.
• Graph Theory by constructing a graph where each node represents a possible sequence configuration and edges represent the ability to place one sequence over another.
• Dynamic Programming to efficiently calculate the number of combinations by avoiding recalculating the same subproblems.

The entire approach revolves around breaking down the problem into manageable subproblems (valid sequences of a single row) and then using the properties of these subproblems (whether they can stack on top of each other) to solve the larger problem (building the entire wall) while avoiding repetitive work through memoization in the DP table.

Example Walkthrough

Let's illustrate the solution approach with a small example where the goal is to build a wall of height 2 and width 4 using bricks of widths 1 and 2. The available brick sizes are represented in the bricks array: [1, 2].

Step 1: Depth-First Search (DFS) for all valid sequences:

We start by generating all sequences of bricks that fit exactly into the width of 4:

• One option is [1, 1, 1, 1] - using four bricks of width 1.
• Another option is [2, 2] - using two bricks of width 2.
• Two more options include [1, 1, 2] and [1, 2, 1], [2, 1, 1] considering different arrangements of width 1 and 2 bricks.

We now have all valid sequences [ [1, 1, 1, 1], [2, 2], [1, 1, 2], [1, 2, 1], [2, 1, 1] ].

Step 2: Sequences Validation:

Using the check function, we will determine which sequences can be placed on top of each other without the joints aligning:

• The sequence [1, 1, 1, 1] can be placed on top of any other sequence since it doesn't create any aligned joints.
• The sequence [2, 2] cannot be placed on top of itself as that would align joints, but it can be placed on top of [1, 1, 2], [1, 2, 1], or [2, 1, 1].
• Similarly, [1, 1, 2] cannot be on top of [2, 2], but it can go on [1, 2, 1] or [2, 1, 1].
• The same logic applies to [1, 2, 1] and [2, 1, 1].

Step 3: Graph Building:

We construct a graph showing which sequences can sit on top of each other:

1g = {
2  0: [1, 2, 3, 4],  // [1, 1, 1, 1] can be placed over any sequence.
3  1: [2, 3, 4],     // [2, 2] can be placed over [1, 1, 2], [1, 2, 1], and [2, 1, 1].
4  2: [0, 3, 4],     // [1, 1, 2] can be placed over [1, 1, 1, 1], [1, 2, 1], and [2, 1, 1].
5  3: [0, 1, 4],     // ...
6  4: [0, 1, 2],
7}

Step 4: Dynamic Programming (DP):

Initialize the DP table. Let dp[i][j] be the number of ways to build up to the i-th height, ending with the j-th sequence:

1    dp = [
2      [1, 1, 1, 1, 1],  // Base case: 1 way to lay each sequence as the first row.
3      [0, 0, 0, 0, 0],  // We will fill this part with the number of ways to make the second row.
4    ]

We iterate over each sequence for the second layer, and add up compatible sequences from the previous layer according to the graph g:

1    dp[1][0] = dp[0][1] + dp[0][2] + dp[0][3] + dp[0][4]  // 4 ways to place the second sequence over the first
2    dp[1][1] = dp[0][0] + dp[0][2] + dp[0][3] + dp[0][4]  // 4 ways
3    dp[1][2] = dp[0][0] + dp[0][3] + dp[0][4]             // 3 ways
4    ...

Now, our DP table looks like this:

1    dp = [
2      [1, 1, 1, 1, 1],
3      [4, 4, 3, 3, 3],
4    ]

Step 5: Summing Up Combinations:

Lastly, we sum the last row in the dp table to find the total number of ways to build the wall to the height of 2:

Total combinations = dp[1][0] + dp[1][1] + dp[1][2] + dp[1][3] + dp[1][4] = 4 + 4 + 3 + 3 + 3 = 17.

Since the answer could be very large, we would normally return this number modulo 10^9 + 7. In our example, the answer is 17.

So, for our small example with a wall of height 2 and width 4 using bricks of width 1 and 2, there are 17 different ways to build a sturdy wall where no two adjacent row joints align (except at the ends).

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity can be divided into a few parts:

1. DFS (dfs function) for generating all possible row combinations: The DFS function is used to generate all possible combinations of bricks that can form a row of the desired width. In the worst case, it generates all permutational combinations. If we denote k as the maximum number of bricks that a row can take, then the time complexity for this step can be approximated as O(b^k), where b is the number of brick sizes in the bricks list.

2. Checking compatibility between two rows (check function): The check function is used to determine if two rows are compatible, which means no vertical cracks align. Every row combination is checked against every other combination. This gives us time complexity of O(n^2 * w) for this part, where n is the total number of unique rows and w is the width of the wall since in the worst scenario each element of a row is checked against each element of another row.

3. Populating the graph with compatible layers: Based on the outputs of the check function, a graph is populated. This is also O(n^2) as each row is checked against every other row for compatibility.

4. Dynamic Programming to calculate the number of ways to build the wall (dp loop): The DP array is filled in height iterations, and each sub-problem depends on the previous layer's sub-problems. We have height * n sub-problems, and each could potentially depend on all n other sub-problems from the previous row. Thus the complexity for this part is O(height * n^2).

Combining all steps, the total time complexity of the code is:

T(height, width, b) = O(b^k) + O(n^2 * w) + O(n^2) + O(height * n^2)

Since the number of unique rows n can be pretty large (up to b^k), the time complexity is dominated by the last term which involves height, leading to a worst-case scenario of:

T(height, width, b) = O(height * b^(2k))

Space Complexity

The space complexity is determined by the storage required for:

1. The s list that stores all possible row combinations: In the worst case, this could store up to b^k combinations.

2. The g defaultdict that stores the adjacency list of the graph: Since we're dealing with n unique rows and each row can be compatible with up to n-1 other rows, in the worst case, this takes O(n^2) space.

3. The dp array: The dp array is a 2D array with height rows and n columns, so it takes O(height * n) space.

4. Additional space for the t list used during DFS and function call stack: The t list and the recursion call stack could in the worst case require O(width) space each due to the recursive calls depending on the width of the wall.

The space complexity of the code is thus the maximum of the space used by these data structures:

S(height, width, b) = max(O(b^k), O(n^2), O(height * n), O(width))

Since n can be as large as b^k, the dominant term is:

S(height, width, b) = O(height * b^(2k)) + O(width)

Considering O(height * b^(2k)) would generally be larger than O(width), we can approximate the space complexity as:

S(height, width, b) = O(height * b^(2k))

Learn more about how to find time and space complexity quickly using problem constraints.