Brick Wall
Problem
Given a list of rows representing a brick wall where each row is a list of brick widths, return the minimum number of bricks that a vertical line crosses when drawn from top to bottom between the bricks.
- 1 ≤ wall.length ≤ 10⁴
- 1 ≤ wall[i].length ≤ 10⁴
- 1 ≤ sum(wall[i]) ≤ 2³¹ - 1
- The sum of widths in each row is the same
Example
wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]2The algorithm counts the positions of brick edges (excluding the rightmost edge) across all rows. For example, the edge positions for the first row are at 1, 3, and 5. The position with the most aligned edges is 3, where 4 rows have edges aligned. Drawing the line at position 3 crosses the fewest bricks, which is total rows (6) minus 4 aligned edges = 2.
Approach
Straightforward Solution
A brute-force approach would check every possible vertical line position across the wall width and count how many bricks it crosses by scanning each row, resulting in O(n * m) time where n is the number of rows and m is the number of bricks per row. This is inefficient for large inputs.
Core Observation
The vertical line crosses a brick if it does not pass through a brick edge. Therefore, minimizing crossed bricks is equivalent to maximizing the number of aligned edges the line passes through.
Path to Optimal
PreviewThe key insight is to track the cumulative edge positions of bricks in each row (excluding the last brick to avoid the wall's right edge)…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewIterate through each row, compute the prefix sums of brick widths to find edge positions, and update a hash map counting how many rows have edges at each position. The answer is the total number of rows minus the maximum edge count found…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n * m)
Each row is processed once, and each brick except the last is visited to compute prefix sums and update the hash map. Hash map operations are O(1) on average.
Space
O(n * m)
In the worst case, all edge positions are unique, requiring storage proportional to the total number of bricks minus the number of rows. This space is necessary to track edge frequencies.
Pattern Spotlight
Hash Maps (Frequency Counting of Prefix Sums)
When minimizing crossings or overlaps along a linear dimension, transform the problem into counting aligned boundaries using prefix sums and hash maps to find the position with maximum alignment efficiently.
Solution
| 1 | class Solution: |
| 2 | def leastBricks(self, wall: list[list[int]]) -> int: |
| 3 | edge_counts = {} |
| 4 | |
| 5 | for row in wall: |
| 6 | edge_position = 0 |
| 7 | |
| 8 | for brick_width in row[:-1]: |
| 9 | edge_position += brick_width |
| 10 | edge_counts[edge_position] = edge_counts.get(edge_position, 0) + 1 |
| 11 | |
| 12 | max_aligned_edges = 0 |
| 13 | |
| 14 | for count in edge_counts.values(): |
| 15 | max_aligned_edges = max(max_aligned_edges, count) |
| 16 | |
| 17 | return len(wall) - max_aligned_edges |
Step-by-Step Solution
Accumulate Edge Positions Across Rows Using Prefix Sums
| 3 | edge_counts = {} |
| 5 | for row in wall: |
| 6 | edge_position = 0 |
| 8 | for brick_width in row[:-1]: |
| 9 | edge_position += brick_width |
| 10 | edge_counts[edge_position] = edge_counts.get(edge_position, 0) + 1 |
Objective
To compute and count the positions of brick edges (excluding the rightmost edge) across all rows to identify where edges align.
Key Insight
By iterating through each brick in a row except the last, summing their widths to find the edge positions, and updating a hash map with counts of how many rows have edges at each position, the algorithm efficiently aggregates alignment information. This approach avoids scanning every possible vertical line position and leverages prefix sums to transform the problem into a frequency counting task.
Interview Quick-Check
Core Logic
Use prefix sums to find edge positions and a hash map to count how many rows share each edge position.
State & Boundaries
Exclude the last brick in each row to avoid counting the wall's right edge.
Common Pitfalls & Bugs
Forgetting to exclude the last brick leads to incorrect counts and invalid line positions.
Determine Maximum Edge Alignment and Compute Result
To find the edge position with the maximum alignment and calculate the minimum number of bricks crossed by the vertical line.
1 more step with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
return len(wall) - max_aligned_edgesReturn the minimum number of bricks crossed by subtracting max aligned edges from total rows.
Subtracting the maximum edge alignment from the total rows yields the minimal number of bricks the vertical line crosses, solving the problem.
for brick_width in row[:-1]:Iterate through each brick in the row except the last one.
Excluding the last brick avoids counting the wall's right edge, which is not a valid line position.
edge_counts[edge_position] = edge_counts.get(edge_position, 0) + 1Increment the count of rows with an edge at the current position in the hash map.
Counting how many rows share an edge at this position identifies potential line placements that minimize brick crossings.
Full line-by-line criticality + rationale for all 10 lines available on Pro.
Test Your Understanding
Why do we exclude the last brick in each row when counting edge positions?
See the answer with Pro.
Related Problems
Hash Maps pattern
Don't just read it. Drill it.
Reconstruct Brick Wall from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Brick Wall drill