LeetCode 554: Brick Wall

Problem Restatement

We are given a rectangular brick wall.

The wall has several rows. Each row contains bricks of different widths, but every row has the same total width.

We need to draw one vertical line from the top of the wall to the bottom.

If the line passes through the middle of a brick, it crosses that brick.

If the line passes exactly through the edge between two bricks, it does not cross a brick in that row.

We cannot draw the line along the far left or far right edge of the wall.

Return the minimum number of bricks the vertical line must cross.

The important rule is that a line through a brick edge is free for that row. So we want to place the line where the most brick edges line up. The problem statement and constraints specify that all rows have the same total width, and the total number of bricks is at most 20000.

Input and Output

Example function shape:

def leastBricks(wall: list[list[int]]) -> int:
    ...

Examples

Example:

wall = [
    [1, 2, 2, 1],
    [3, 1, 2],
    [1, 3, 2],
    [2, 4],
    [3, 1, 2],
    [1, 3, 1, 1],
]

All rows have total width 6.

Now look at the internal brick edges.

For the first row:

[1, 2, 2, 1]

The internal edge positions are:

1
1 + 2 = 3
1 + 2 + 2 = 5

We do not include position 6, because that is the right wall edge.

For all rows, the internal edge positions are:

The edge counts are:

The best position is 4, where four rows have a brick edge.

There are six rows total, so the line crosses:

6 - 4 = 2

bricks.

So the answer is:

2

First Thought: Try Every Vertical Position

One direct idea is to try every possible vertical position inside the wall.

For each position, count how many rows do not have an edge there. Those rows are crossed by the line.

This is logically correct, but it can be too slow because the wall width can be large. Brick widths are integers, and the total width can be much larger than the number of bricks.

We should not iterate over every coordinate. We only care about coordinates where brick edges occur.

Key Insight

A vertical line crosses fewer bricks when it passes through more internal brick edges.

So instead of counting crossed bricks directly, count aligned edges.

If a line is placed at position x and k rows have an internal edge at x, then the line does not cross those k rows.

If the wall has h rows, then the line crosses:

h - k

bricks.

To minimize crossed bricks, maximize k.

So the answer is:

number_of_rows - maximum_edge_frequency

We must ignore the final edge of each row, because drawing along the right boundary is not allowed.

Algorithm

Create a hash map called edge_count.

For each row:

1. Start with position = 0.
2. Iterate through every brick except the last brick.
3. Add the brick width to position.
4. Increment edge_count[position].

After processing all rows:

1. Find the largest value in edge_count.
2. Return len(wall) - largest_value.

If there are no internal edges, then edge_count is empty. That means every row has exactly one brick. Any valid vertical line crosses every row, so the answer is len(wall).

Correctness

Each internal edge position represents a place where a vertical line can pass through a gap in that row.

For a fixed vertical position x, suppose edge_count[x] = k. That means exactly k rows have a brick edge at x. In those rows, the line crosses no brick. In all other rows, the line must pass through the interior of some brick, because every row covers the full wall width.

Therefore, drawing the line at x crosses exactly:

len(wall) - edge_count[x]

bricks.

The optimal line must be placed at an internal edge position if it wants to avoid crossing at least one row. If a line is placed at a position with no internal edge, then it crosses every row. Such a position cannot be better than the most frequent internal edge position, unless no internal edge exists at all.

The algorithm counts every allowed internal edge position and chooses the position with the largest frequency. Therefore, it maximizes the number of rows avoided and minimizes the number of bricks crossed.

Complexity

Let m be the total number of bricks in the wall.

Implementation

from collections import defaultdict
from typing import List

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        edge_count = defaultdict(int)

        for row in wall:
            position = 0

            for width in row[:-1]:
                position += width
                edge_count[position] += 1

        max_edges = max(edge_count.values(), default=0)

        return len(wall) - max_edges

Code Explanation

We use a hash map:

edge_count = defaultdict(int)

The key is an internal edge position.

The value is how many rows have an edge at that position.

For each row, we compute prefix sums:

position = 0

for width in row[:-1]:
    position += width
    edge_count[position] += 1

The slice row[:-1] is important.

It skips the last brick, because after the last brick we reach the right edge of the wall. The problem does not allow drawing the line along the wall boundary.

After all rows are processed, we find the largest number of aligned edges:

max_edges = max(edge_count.values(), default=0)

The default=0 handles the case where every row has only one brick.

Finally:

return len(wall) - max_edges

The total number of rows minus the largest number of avoided rows gives the minimum number of crossed bricks.

Testing

def run_tests():
    s = Solution()

    assert s.leastBricks([
        [1, 2, 2, 1],
        [3, 1, 2],
        [1, 3, 2],
        [2, 4],
        [3, 1, 2],
        [1, 3, 1, 1],
    ]) == 2

    assert s.leastBricks([[1], [1], [1]]) == 3
    assert s.leastBricks([[1, 1], [1, 1], [1, 1]]) == 0
    assert s.leastBricks([[2, 3], [1, 4], [3, 2]]) == 2
    assert s.leastBricks([[1, 2, 1], [2, 2], [3, 1]]) == 1

    print("all tests passed")

run_tests()