Brick Wall - Video Solutions

Problem Overview: You are given a wall represented as rows of brick widths. The goal is to draw a vertical line from top to bottom that crosses the fewest bricks. If the line passes exactly through the edge between two bricks, it does not count as crossing a brick.

The key observation: crossing fewer bricks means aligning the vertical line with as many brick edges as possible. Every time multiple rows share the same edge position, you avoid crossing those bricks.

Approach 1: Prefix Sum and HashMap (Optimal) (Time: O(N), Space: O(N))

Iterate through each row and compute cumulative brick widths using a prefix sum. Each prefix sum represents a potential edge position where a vertical line could pass. Store the frequency of these edge positions in a HashMap. The last edge in each row is ignored because the line cannot be placed at the wall boundary. The position with the highest frequency means the line passes through the most edges, so the number of crossed bricks becomes rows - maxEdgeFrequency. This approach works efficiently because each brick is processed exactly once, making it linear with respect to the total number of bricks.

This method relies on quick hash lookups to count edge occurrences and is a common technique when solving frequency problems with hash tables. The prefix accumulation step is a direct application of array traversal patterns.

Approach 2: Dynamic Programming Perspective (Time: O(N), Space: O(N))

The same idea can be framed as a dynamic programming accumulation of edge positions. Instead of thinking purely in terms of frequency counting, treat each prefix width as a state representing a candidate cut position. As you iterate row by row, update the count for each position and track the best state seen so far. The "DP state" stores how many rows share that boundary. While the underlying implementation still uses a map, this perspective helps when extending the problem or combining it with other row‑based transitions often seen in dynamic programming.

Compared to brute force attempts that test every possible column position across the wall, this approach avoids scanning the entire width repeatedly. Instead, it only considers natural breakpoints created by brick edges.

Recommended for interviews: The prefix sum + hash map approach is the expected solution. It demonstrates recognition of shared edge boundaries and efficient counting using constant‑time hash lookups. A brute force scan across the wall width shows baseline reasoning, but identifying that edges are the only meaningful positions shows stronger algorithmic insight.