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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Brick Wall

Number: 554

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Agoda, Meta

Problem Description

Given a brick wall represented as a list of rows with each row containing brick widths, draw a vertical line from the top to the bottom of the wall such that it crosses the least number of bricks. If the line goes through the edge between bricks, that brick is not counted as crossed. The line cannot be drawn along the two vertical edges of the wall. Return the minimum number of crossed bricks after drawing such a vertical line.

Key Insights

  • The optimal vertical line should pass through as many brick gaps (edges) as possible.
  • For every row, calculate the running sum of brick widths (except for the last brick) to record potential gap positions.
  • Use a hash table (or dictionary) to count how many times each gap position occurs across all rows.
  • The answer is the number of rows minus the maximum count of gaps that align vertically, since that minimizes the number of bricks crossed.

Space and Time Complexity

Time Complexity: O(N) where N is the total number of bricks (sum of lengths of all rows), since each brick in each row is processed once. Space Complexity: O(M) where M is the number of unique gap positions, which in the worst-case could be proportional to N.

Solution

We iterate through each row and calculate the cumulative sum of brick widths, ignoring the last brick to avoid counting the wall edge. These cumulative sums mark potential vertical gap positions. We use a hash table to keep track of how many rows have a gap at each position. The optimal vertical line goes where the gap count is maximal and thus crosses the minimal number of bricks, which is given by the total number of rows minus this maximum gap count.

Code Solutions

# Function to compute the minimum number of bricks the vertical line crosses.
def leastBricks(wall):
    # Dictionary to count gap positions.
    gap_count = {}
    
    # Iterate through each row in the wall.
    for row in wall:
        cumulative_sum = 0
        # Iterate through the row, omit the last brick as it represents the right edge.
        for brick in row[:-1]:
            cumulative_sum += brick
            # Increment the count of this particular gap.
            gap_count[cumulative_sum] = gap_count.get(cumulative_sum, 0) + 1
    
    # If no gap exists, the line crosses all rows.
    if not gap_count:
        return len(wall)
    
    # Get the maximum number of gaps at any position.
    max_gaps = max(gap_count.values())
    # The minimum bricks crossed is the total rows minus the maximum gap count.
    return len(wall) - max_gaps

# Example usage:
wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
print(leastBricks(wall))  # Output: 2
← Back to All Questions