Problem Description

You have a rectangular brick wall with n rows of bricks. Each row contains bricks of the same height (1 unit) but potentially different widths. All rows have the same total width.

Your task is to draw a vertical line from top to bottom that crosses the least number of bricks. When the line passes through the edge between two bricks, it doesn't count as crossing a brick - only when it goes through the middle of a brick does it count as crossed. You cannot draw the line along the outer edges of the wall.

Given a 2D array wall where wall[i] represents the widths of bricks in row i, return the minimum number of bricks that must be crossed.

For example, if you have a wall where row 1 has bricks of widths [1, 2, 2, 1] and row 2 has bricks of widths [3, 1, 2], both rows sum to 6. You could draw a line at position 3 from the left, which would pass through the edge between bricks in both rows (after the first brick of width 3 in row 2, and after bricks of width 1+2 in row 1), crossing 0 bricks total.

The solution uses a hash table to count how many rows have a brick edge at each position. By tracking the cumulative sum of brick widths in each row (excluding the last brick since we can't draw on the wall's edge), we find which position has the most brick edges aligned. The position with the most edges means the fewest bricks crossed. The answer is the total number of rows minus the maximum count of aligned edges.

Intuition

The key insight is to think about this problem inversely - instead of finding where to cross the most bricks, we should find where to cross the fewest bricks. And crossing the fewest bricks means finding where the most brick edges align vertically.

Think about it this way: if we draw a vertical line at any position, it will either go through the middle of a brick (crossing it) or through an edge between two bricks (not crossing). For each row, we have certain positions where brick edges exist. If multiple rows have edges at the same position, a vertical line drawn there would pass through those edges without crossing bricks.

To find these edge positions, we can use prefix sums. For each row, as we traverse from left to right, we keep a running sum of brick widths. Each cumulative sum represents a position where an edge exists (except for the last brick, since that would be the wall's edge).

For example, if a row has bricks [1, 2, 2, 1], the edges are at positions 1 (after first brick), 3 (after first two bricks), and 5 (after first three bricks). We don't count position 6 as that's the wall edge.

By counting how many times each edge position appears across all rows using a hash table, we can identify the position with the maximum number of aligned edges. Drawing the line there minimizes brick crossings. The number of bricks crossed equals the total number of rows minus the number of rows that have an edge at that optimal position.

This transforms the problem from "minimize crossings" to "maximize edge alignments," which is much easier to solve with a frequency counting approach.

Solution Approach

The solution uses a hash table combined with prefix sum calculation to efficiently find the optimal vertical line position.

Implementation Steps:

1. Initialize a Counter: Create a hash table cnt using Python's Counter() to store the frequency of each edge position across all rows.

2. Process Each Row: For each row in the wall:

   • Initialize a running sum s = 0 to track the cumulative position
   • Iterate through all bricks except the last one using row[:-1]
   • For each brick width x, add it to the running sum: s += x
   • Record this edge position in the counter: cnt[s] += 1

3. Calculate Minimum Crossings:

   • Find the maximum frequency in cnt using max(cnt.values(), default=0)
   • The default=0 handles the edge case where all rows have only one brick
   • Return len(wall) - max_frequency

Why This Works:

• The prefix sum s at each iteration represents the x-coordinate where an edge exists after placing bricks from left to right
• By excluding the last brick (row[:-1]), we avoid counting the wall's right edge
• The position with the highest count in cnt is where the most edges align vertically
• If we draw a line at that position, it passes through edges (not bricks) for all rows that contributed to that count
• The remaining rows (len(wall) - max_count) are the ones where the line must cross through a brick

Time Complexity: O(n × m) where n is the number of rows and m is the average number of bricks per row.

Space Complexity: O(k) where k is the number of unique edge positions across all rows.

Example Walkthrough

Let's walk through a small example with a wall that has 3 rows:

• Row 1: [1, 2, 1] (bricks of width 1, 2, and 1)
• Row 2: [1, 1, 2] (bricks of width 1, 1, and 2)
• Row 3: [2, 2] (bricks of width 2 and 2)

All rows sum to 4, representing the total wall width.

Step 1: Initialize Counter Create an empty counter cnt = {} to track edge positions.

Step 2: Process Each Row

Row 1: [1, 2, 1]

• Start with s = 0
• First brick (width 1): s = 0 + 1 = 1, record edge at position 1
• Second brick (width 2): s = 1 + 2 = 3, record edge at position 3
• Skip last brick (width 1) as it ends at the wall edge
• Counter: cnt = {1: 1, 3: 1}

Row 2: [1, 1, 2]

• Start with s = 0
• First brick (width 1): s = 0 + 1 = 1, record edge at position 1
• Second brick (width 1): s = 1 + 1 = 2, record edge at position 2
• Skip last brick (width 2)
• Counter: cnt = {1: 2, 3: 1, 2: 1}

Row 3: [2, 2]

• Start with s = 0
• First brick (width 2): s = 0 + 2 = 2, record edge at position 2
• Skip last brick (width 2)
• Counter: cnt = {1: 2, 3: 1, 2: 2}

Step 3: Find Optimal Position

• Position 1 has 2 edges aligned
• Position 2 has 2 edges aligned
• Position 3 has 1 edge aligned
• Maximum alignment is 2 (at positions 1 or 2)

Step 4: Calculate Result

• Total rows: 3
• Maximum edge alignment: 2
• Minimum bricks crossed: 3 - 2 = 1

If we draw a line at position 1:

• Row 1: passes through edge (no crossing)
• Row 2: passes through edge (no crossing)
• Row 3: passes through middle of first brick (1 crossing)

Total: 1 brick crossed, which matches our calculation!

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m is the number of rows in the wall and n is the total number of bricks across all rows. This is because the algorithm uses nested loops - the outer loop iterates through each row (m iterations), and the inner loop iterates through each brick in that row (excluding the last one). In the worst case, we process every brick in the wall exactly once.

The space complexity is O(n), where n represents the number of unique edge positions (gaps between bricks) that can exist in the wall. The Counter dictionary cnt stores each unique position where edges align. In the worst case, if all bricks have different widths and create unique edge positions, the space required would be proportional to the total number of bricks minus the number of rows (since we exclude the last brick in each row from consideration).

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

Common Pitfalls

1. Including the Wall's Right Edge

One of the most common mistakes is iterating through all bricks in each row instead of excluding the last one. This would incorrectly count the wall's right edge as a valid position for drawing the line.

Incorrect approach:

for brick_width in row:  # Wrong: includes the last brick
    cumulative_position += brick_width
    edge_count[cumulative_position] += 1

Correct approach:

for brick_width in row[:-1]:  # Correct: excludes the last brick
    cumulative_position += brick_width
    edge_count[cumulative_position] += 1

2. Handling Empty Counter Edge Case

When all rows contain only a single brick, the counter remains empty since there are no internal edges. Using max(edge_count.values()) directly would raise a ValueError on an empty sequence.

Incorrect approach:

return len(wall) - max(edge_count.values())  # Crashes if edge_count is empty

Correct approach:

return len(wall) - max(edge_count.values(), default=0)  # Returns len(wall) when no edges exist

3. Misunderstanding the Problem - Counting Crossings Instead of Edges

Some might mistakenly try to count how many bricks are crossed at each position rather than counting where edges align. Remember that the goal is to find where the most edges line up, not to directly count brick crossings.

Incorrect mental model: Tracking which bricks are crossed at each x-coordinate.

Correct mental model: Tracking where brick edges occur, then choosing the position with the most edges.

4. Off-by-One Error in Position Calculation

Ensure the cumulative sum starts at 0 and is updated before recording. Starting with the wrong initial value or updating in the wrong order can shift all positions incorrectly.

Incorrect approach:

cumulative_position = 1  # Wrong starting position

Correct approach:

cumulative_position = 0  # Start from the left edge