Brick Wall

Brick Wall

What is this problem about?

Imagine a brick wall made of several rows of bricks. Each row has the same total width, but the bricks in each row have different widths. You want to draw a vertical line from top to bottom that crosses the fewest number of bricks. The line cannot be drawn at the very edges of the wall.

Why is this asked in interviews?

This is a popular question at companies like Bloomberg, Amazon, and Meta. It tests your ability to think "laterally." Instead of counting how many bricks you cross, you should count how many edges (gaps between bricks) you align with. This shift in perspective turns a geometric problem into a Hash Table frequency problem.

Algorithmic pattern used

This problem uses the Hash Table / Frequency Map pattern. For each row, you calculate the cumulative sum of the brick widths (which represents the positions of the edges). You store the frequency of each edge position in a map. The position with the highest frequency is where you should draw your line, as it passes through the most gaps and thus the fewest bricks.

Example explanation

Wall: Row 1: [1, 2, 2, 1] -> Edges at: 1, 3, 5 Row 2: [3, 1, 2] -> Edges at: 3, 4 Row 3: [1, 3, 2] -> Edges at: 1, 4

Frequency Map: Edge 1: 2 times Edge 3: 2 times Edge 4: 2 times Edge 5: 1 time

Maximum edge frequency is 2. The wall height is 3. Minimum bricks crossed = Total Rows - Max Edges = 3 - 2 = 1.

Common mistakes candidates make

The most common error is including the last edge (the end of the wall) in the map. The problem specifically says you cannot draw the line at the edges. Another mistake is using nested loops that result in $O(W)$ time (where $W$ is the width of the wall), which is too slow if the bricks are thin and the wall is wide. The hash table approach is $O(N)$, where $N$ is the total number of bricks.

Interview preparation tip

When a problem asks to "minimize intersections," look for "maximum alignments." Counting gaps or edges is often much easier than counting overlaps. This "complementary" thinking is a key skill for optimizing spatial algorithms.