Number of Ways to Build Sturdy Brick Wall

Medium

Asked by:

18 views

Topics:

Dynamic Programming

You are given two integers height and width representing the height and width of a brick wall respectively. The wall is made up of rows of bricks of the same height 1.

You are given an array bricks where bricks[i] is the width of the i^th brick. You can use an unlimited number of bricks of each width.

You want to build the wall such that it satisfies the following conditions:

Each row in the wall must have the exact same width.
For each row, the sum of the widths of the bricks in that row must be equal to width.
Each row must consist of at least two bricks.
The bricks on the same row should be arranged in the order as they appear in bricks.

Return the number of ways to build a sturdy brick wall. Since the answer may be very large, return it modulo 10⁹ + 7.

A brick wall is considered sturdy if there is no vertical line going through all rows of bricks. In other words, there should not exist any vertical line from top to bottom that crosses all rows without crossing any bricks.

Example 1:

Input: height = 3, width = 2, bricks = [1,2]
Output: 3
Explanation: The possible ways to build the wall are:
[1, 1]
[2]

[2]
[1, 1]

[1, 1]
[1, 1]

Since all of the walls have a vertical line going through all of the rows, the number of sturdy brick walls is 3.

Example 2:

Input: height = 1, width = 1, bricks = [1]
Output: 0
Explanation: Since we cannot build any row of bricks with width equals to 1, the answer is 0.

Constraints:

1 <= height <= 100
1 <= width <= 10
1 <= bricks.length <= 10
1 <= bricks[i] <= width

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the specific constraints on the height and width of the wall (e.g., maximum/minimum values)?
Are all brick lengths positive integers, and what is the possible range of lengths?
What should I return if it's impossible to build a valid sturdy wall according to the problem definition (e.g., no valid arrangement of bricks)?
Are gaps allowed between bricks in the same row, or must each row be completely filled?
Is the definition of 'sturdy' referring exclusively to the vertical alignment of bricks, or are there other factors to consider?

Brute Force Solution

Approach

The brute force approach to building a sturdy brick wall involves trying every conceivable wall configuration. It's like physically building every possible wall, one at a time, to see which ones meet the criteria. We will exhaustively explore all combinations.

Here's how the algorithm would work step-by-step:

Imagine you have a large supply of bricks of varying widths.
Start with the first row. Try placing just one brick. Then try placing two bricks next to each other, then three, and so on, until the total width of the row is reached.
For each of these possible first rows, consider all possible arrangements of bricks for the second row.
Keep doing this for each row of the wall, exploring all combinations of bricks.
After building each potential wall, check if it's 'sturdy' according to the rules. A wall is sturdy if it doesn't have any continuous vertical crack running through it.
Count how many walls you built that turned out to be sturdy.
The total count of sturdy walls is your answer.

Code Implementation

def number_of_ways_to_build_sturdy_brick_wall_brute_force(height, width):    total_sturdy_walls = 0

    def is_wall_sturdy(wall):        for column_index in range(1, width):            crack_found = True            for row_index in range(height):                row = wall[row_index]
                total_width = 0
                for brick_width in row:
                    total_width += brick_width
                    if total_width == column_index:
                        crack_found = False
                        break                if crack_found:
                    break            if crack_found:
                return True
        return False
    def generate_rows(current_row, current_width):        if current_width == width:
            return [current_row]
        if current_width > width:
            return []

        row_arrangements = []        for brick_width in range(1, width + 1):            remaining_width = current_width + brick_width
            if remaining_width <= width:                new_row = current_row + [brick_width]
                row_arrangements.extend(generate_rows(new_row, remaining_width))        return row_arrangements    def generate_walls(current_wall):        if len(current_wall) == height:
            if is_wall_sturdy(current_wall):                return 1            else:
                return 0        # Generate all possible rows for the next level        row_arrangements = generate_rows([], 0)        sturdy_wall_count = 0        # Try to add it to the wall and recurse        for row in row_arrangements:
            sturdy_wall_count += generate_walls(current_wall + [row])        return sturdy_wall_count    # Count all the possible walls    total_sturdy_walls = generate_walls([])    return total_sturdy_walls

Big(O) Analysis

Time Complexity

O(W^H) – The brute force approach explores all possible brick arrangements for each row of the wall. Let W be the width of the wall and H be the height (number of rows). For each row, the number of possible arrangements grows exponentially with W, since each position can either be the start of a new brick or a continuation of a previous one. Since we have H rows, and we explore all possible arrangements for each row, the total number of wall configurations we generate is proportional to the number of possible row arrangements raised to the power of H. Thus, the overall time complexity becomes O(W^H), where W represents width and H represents height.

Space Complexity

O(W^H) – The brute force approach recursively explores all possible wall configurations. Each recursive call represents a row in the wall. The maximum recursion depth is H, where H is the height of the wall (number of rows). For each row, we explore all possible arrangements of bricks whose widths sum up to W, where W is the width of the wall. In the worst-case scenario, we might need to store the configurations of each row, leading to a space complexity of O(W^H) where W represents the total number of ways to create a single row that sums to width W, since for each of the H rows we need to store all possible combinations, where the number of combination for a given row is O(W). The auxiliary space used is dominated by the recursion call stack and the storage of potentially all valid configurations at each row.

Optimal Solution

Approach

The goal is to find the number of ways to build a sturdy brick wall of a given height and width, where a sturdy wall has vertical cracks that don't align across rows. The key is to use dynamic programming to avoid recomputing redundant calculations and only considering valid row configurations.

Here's how the algorithm would work step-by-step:

First, determine all possible valid configurations for a single row. A valid configuration is a combination of brick widths that add up to the total wall width.
Next, find all pairs of valid row configurations that *cannot* be stacked on top of each other. Two rows cannot be stacked if they have a crack in the same position. In other words, identify rows that would cause vertical cracks to align.
Now, use dynamic programming. The state represents the number of ways to build a wall of a specific height, ending with a specific row configuration.
Start with the base case: for a wall of height 1, the number of ways to build it ending with a specific row configuration is 1 (if that configuration is valid, 0 otherwise).
Iterate through the remaining wall heights, building the solution from the ground up. For each height, consider all possible row configurations and check which valid row configurations can be placed directly *below* the current configuration (i.e., which do not align).
The total number of ways to build the entire wall is the sum of ways to build the wall of the required height ending with each of the possible valid row configurations.
By pre-calculating valid row configurations and their incompatibility, and by using dynamic programming, we efficiently determine the number of sturdy brick wall arrangements without brute-force enumeration.

Code Implementation

def number_of_ways_to_build_wall(height, width):
    def get_valid_row_configurations(width):
        valid_configurations = []
        def find_configurations(current_width, current_configuration):
            if current_width == width:
                valid_configurations.append(tuple(current_configuration))
                return
            if current_width > width:
                return
            for brick_width in range(1, width):
                find_configurations(current_width + brick_width, current_configuration + [brick_width])

        find_configurations(0, [])
        # Only keep configurations that sum up to the full width.
        valid_configurations = [config for config in valid_configurations if sum(config) == width]
        valid_configurations = list(set(valid_configurations))
        return valid_configurations

    valid_row_configurations = get_valid_row_configurations(width)
    number_of_configurations = len(valid_row_configurations)

    def are_rows_compatible(row1, row2):
        crack_positions_row1 = set()
        current_position = 0
        for brick_width in row1:
            current_position += brick_width
            if current_position < width:
                crack_positions_row1.add(current_position)

        crack_positions_row2 = set()
        current_position = 0
        for brick_width in row2:
            current_position += brick_width
            if current_position < width:
                crack_positions_row2.add(current_position)

        # Check if any crack positions are the same.
        return not bool(crack_positions_row1.intersection(crack_positions_row2))

    # dp[i][j] is ways to build wall of height i ending with config j.
    dp = [[0] * number_of_configurations for _ in range(height + 1)]

    # Base case: height 1, each configuration has one way.
    for j in range(number_of_configurations):
        dp[1][j] = 1

    # Iterate to build up the DP table
    for i in range(2, height + 1):
        for j in range(number_of_configurations):
            # Check for compatibility
            for k in range(number_of_configurations):
                if are_rows_compatible(valid_row_configurations[j], valid_row_configurations[k]):
                    dp[i][j] += dp[i - 1][k]

    # Sum of all ways to end with a given config
    total_ways = sum(dp[height])
    return total_ways

Big(O) Analysis

Time Complexity

O(height * row_configs^2) – Let height be the height of the wall and row_configs be the number of valid configurations for a single row. The algorithm involves a dynamic programming approach where we iterate through each height from 1 to height. For each height, we iterate through all possible row configurations (row_configs). For each row configuration, we check its compatibility with every other row configuration (row_configs). Thus, the runtime is approximately height * row_configs * row_configs. Simplifying this, we obtain O(height * row_configs^2).

Space Complexity

O(W * H) – The algorithm uses dynamic programming with a DP table to store the number of ways to build a wall of a specific height ending with a specific row configuration. The number of rows is related to the width (W) of the wall, since each valid row configuration can be considered a row type, and the maximum height of the wall is H. Therefore, the DP table has dimensions proportional to W and H, resulting in O(W * H) space. Additionally, pre-calculating valid row configurations and incompatible row pairs requires extra memory dependent on the wall width W. Because the DP table is the dominant space factor, the space complexity is O(W * H).

Edge Cases

Case	How to Handle
Zero wall height or zero wall width	Return 0 ways as a wall with no height or width is not possible.
Wall height of 1	The number of ways is equivalent to the number of valid row configurations, which can be precomputed efficiently.
Wall width of 1	There is only one way to build the wall regardless of height since each row must have a brick of width 1.
Large wall height and width (scaling)	Use dynamic programming with memoization to avoid redundant calculations and achieve better time complexity (avoiding exponential explosion).
No valid row configurations possible for given width	Return 0 ways as it's impossible to construct any valid wall.
Integer overflow when calculating number of ways	Use modulo operator with a prime number (e.g., 10^9 + 7) to prevent overflow.
All bricks are of size 1	Check all configurations and return results based on problem statement.
Highly skewed brick size distribution (e.g., only 1 and width-1)	The algorithm must efficiently enumerate possible row configurations even with skewed distributions by potentially pruning invalid branches early.

Zero wall height or zero wall width

How to Handle:

Return 0 ways as a wall with no height or width is not possible.

Wall height of 1

How to Handle:

The number of ways is equivalent to the number of valid row configurations, which can be precomputed efficiently.

Wall width of 1

How to Handle:

There is only one way to build the wall regardless of height since each row must have a brick of width 1.

Large wall height and width (scaling)

How to Handle:

Use dynamic programming with memoization to avoid redundant calculations and achieve better time complexity (avoiding exponential explosion).

No valid row configurations possible for given width

How to Handle:

Return 0 ways as it's impossible to construct any valid wall.

Integer overflow when calculating number of ways

How to Handle:

Use modulo operator with a prime number (e.g., 10^9 + 7) to prevent overflow.

All bricks are of size 1

How to Handle:

Check all configurations and return results based on problem statement.

Highly skewed brick size distribution (e.g., only 1 and width-1)

How to Handle:

The algorithm must efficiently enumerate possible row configurations even with skewed distributions by potentially pruning invalid branches early.