Problem Statement

Brick Wall

Picture a brick wall made of rows. Each row is a list of brick widths, like [1,2,2,1]. The rows all add up to the same total width, but the bricks line up differently in each row. Your job is to draw one straight vertical line from the top of the wall to the bottom, and you want that line to cut through as few bricks as possible. You are not allowed to draw the line along the very left or very right edge of the wall, that would be cheating since it crosses zero bricks. Here is the trick that makes this easy. Instead of trying to count the bricks the line breaks, count the gaps it can slip through. A gap is the seam where two bricks meet inside a row. If the line passes through a seam in a row, it does not break a brick in that row. So the best line is the one that lines up with the most seams. A hash map (a lookup table that pairs a key with a value, here a horizontal position paired with how many rows have a seam there) lets us tally up the seams at every position. The answer is the total number of rows minus the most seams found at any single position, because every row where the line hits a seam is a row where it did not break a brick.

mediumHash TableArrays & HashingTime: O(n) · Space: O(n)

Signals to notice

find minimum bricks crossed by vertical linemaximize gaps alignedcount gap positions

Brute force first

Try every possible x-position — O(n × width).

The key insight

For each row, compute prefix sums (gap positions). Count gaps at each x-position using a hash map. The x with the most gaps crosses the fewest bricks. Answer = rows - maxGaps. O(total bricks).

Trace it on `wall=[[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]`

init edge_count={}; iterate rows summing prefixes, skip last brick of each row
row [1,2,2,1]: edges at 1,3,5 -> {1:1, 3:1, 5:1}
row [3,1,2]: edges at 3,4 -> {1:1, 3:2, 5:1, 4:1}
row [1,3,2]: edges at 1,4 -> {1:2, 3:2, 5:1, 4:2}
row [2,4]: edge at 2 -> {1:2, 3:2, 5:1, 4:2, 2:1}
row [3,1,2]: edges at 3,4 -> {1:2, 3:3, 5:1, 4:3, 2:1}
row [1,3,1,1]: edges at 1,4,5 -> {1:3, 3:3, 5:2, 4:4, 2:1}
max_edges=4 (position 4); return len(wall)-max_edges = 6-4 = 2

What must stay true

A vertical line crosses a brick unless it passes through a gap. Maximizing gaps aligned at the same x-position minimizes bricks crossed.

Shape of the loop

edge_count = {}
for row in wall:
    pos = 0
    for brick in row[:-1]:          # skip last brick (wall edge)
        pos += brick
        edge_count[pos] = edge_count.get(pos, 0) + 1   # tally gaps at this x
return len(wall) - max(edge_count.values() or [0])

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Counting bricks instead of gaps — count gaps, then bricks crossed = total rows - max gaps at any x.

Arrays & Hashing Pattern