We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Ways to Build Sturdy Brick Wall

Number: 2322

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

You need to build a wall with a given height and width using bricks of fixed height (1) but varying widths (given in the bricks array). Each row of the wall must exactly fill the width. Furthermore, to ensure the wall is sturdy, no two adjacent rows can have brick joints (the boundaries where one brick ends and the next begins) line up at the same position except at the two ends. Return the number of ways to build such a sturdy wall modulo 10^9 + 7.

Key Insights

  • First, generate all valid ways (configurations) to fill a row. Each configuration can be represented as a bitmask where bits represent positions (from 1 to width-1) of brick joints.
  • Use recursion/backtracking to construct rows by placing bricks sequentially and recording the join positions (except at position 0 and width).
  • Two rows (bitmask configurations) are compatible if they do not have a joint at the same position; in other words, the bitwise AND of the two bitmasks is zero.
  • Use dynamic programming over the height of the wall where each state represents the current row configuration.
  • Precompute a compatibility graph (or list) to quickly iterate over valid transitions from one row configuration to the next.

Space and Time Complexity

Time Complexity: O(height * R^2) where R is the number of valid row configurations (R is small since width ≤ 10).
Space Complexity: O(height * R) for the dynamic programming table along with O(R^2) for compatibility storage.

Solution

We begin by generating all valid row configurations by recursively placing bricks from a given position until we reach the wall’s width. Each time we place a brick, if we have not reached the end of the row, we mark the join position in a bitmask. Next, we build a compatibility list to record which pairs of configurations can be stacked (their bitmasks must have no common 1 bits). Finally, we use a DP approach where dp[row][config] represents the number of ways to construct the wall up to that row with the ending row using configuration config. The initial row is filled with any valid configuration, and we then “stack” rows by adding only those configurations that are compatible with the previous one. Sum up all possibilities for the final row and take modulo 10^9 + 7.

Code Solutions

# Python solution with detailed comments
MOD = 10**9 + 7

def numberOfWays(height, width, bricks):
    valid_configs = []

    # Helper function to generate valid row configurations using recursion/backtracking.
    # pos: current position in the row; config: bitmask representing brick joints (excluding 0 and width)
    def dfs(pos, config):
        # If we've reached the exact width, add the configuration
        if pos == width:
            valid_configs.append(config)
            return
        # Try all bricks that can fit from current position
        for brick in bricks:
            next_pos = pos + brick
            if next_pos > width:
                continue
            # Compute new configuration; if not at the end of the row, mark the join position bit.
            new_config = config
            if next_pos < width:
                # Position next_pos translates to bit index (next_pos-1)
                new_config |= (1 << (next_pos - 1))
            dfs(next_pos, new_config)

    # Start from position 0 with an empty configuration.
    dfs(0, 0)

    # If no valid row configuration exists, return 0
    if not valid_configs:
        return 0

    R = len(valid_configs)
    
    # Precompute which configurations are compatible 
    # Two configurations are compatible if they have no common set bits (i.e. no brick joint aligns)
    compatibility = [[] for _ in range(R)]
    for i in range(R):
        for j in range(R):
            if valid_configs[i] & valid_configs[j] == 0:
                compatibility[i].append(j)
    
    # dp[row][i]: number of ways to build rows up to 'row' with configuration valid_configs[i] at that row.
    dp = [[0] * R for _ in range(height)]
    
    # Base case: filling the first row with any valid configuration.
    for i in range(R):
        dp[0][i] = 1
    
    # Fill dp table row by row using the compatibility list.
    for row in range(1, height):
        for prev in range(R):
            if dp[row-1][prev] > 0:
                for curr in compatibility[prev]:
                    dp[row][curr] = (dp[row][curr] + dp[row-1][prev]) % MOD

    # Sum up the ways to build the wall and return modulo MOD.
    result = sum(dp[height-1]) % MOD
    return result

# Example usage:
print(numberOfWays(2, 3, [1,2]))  # Expected output: 2
print(numberOfWays(1, 1, [5]))    # Expected output: 0
← Back to All Questions