Brick Wall — Counting Gap Positions With a Frequency Map

Problem Statement#

There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the top to the bottom of the wall that crosses the fewest bricks. The line cannot pass through the edge of the wall, and it must go through all rows.

Each row's bricks are represented as a list of integers giving the brick widths from left to right. The sum of widths in each row equals the total wall width.

Return the minimum number of crossed bricks after drawing such a vertical line.

Constraints:

• n == wall.length
• 1 <= n <= 10^4
• 1 <= wall[i].length <= 10^4
• 1 <= sum(wall[i].length) <= 2 * 10^4
• sum(wall[i]) is the same for each row i.
• 1 <= wall[i][j] <= 2^31 - 1

Example 1:
Input:  wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
Output: 2

Example 2:
Input:  wall = [[1],[1],[1]]
Output: 3
Explanation: Any vertical line must cross all bricks (no internal gaps).

Example 3:
Input:  wall = [[2,1],[1,2]]
Output: 1
Explanation: The line at position 2 crosses 1 brick in row 2 and goes through the gap in row 1.

Why This Problem Matters#

Brick Wall is one of the best examples of reframing a problem to reveal a simpler algorithm. The naive interpretation — find the vertical line that crosses the fewest bricks — feels like it requires checking every possible position and counting brick crossings. But the key insight is that crossing a brick is the complement of hitting a gap. If a vertical line hits a gap in g rows, it crosses bricks in n - g rows. So minimizing brick crossings is equivalent to maximizing gap hits.

Google and Facebook use this problem to test whether candidates can identify this complementary relationship. Candidates who miss it iterate over every possible x-position and count crossings — O(n * W) where W is the wall width. Candidates who see it immediately build a gap frequency map and find the maximum — O(n) total, where n is the total number of bricks.

The gap-frequency pattern generalizes broadly. Whenever you have multiple objects (rows, sequences, paths) and you want to find a "cutting line" that avoids as many objects as possible, the approach is: convert each object to its boundary positions, count boundary frequencies with a map, and find the most common boundary. This appears in interval scheduling, event processing, and even some database query optimization problems.

The problem also teaches a subtle input-parsing habit: gap positions are at cumulative sums of brick widths within each row, excluding the last brick (the wall's edge). Forgetting to exclude the wall edge is the most common mistake.

The Core Insight#

Reframe the problem: instead of counting brick crossings, count gap hits. A vertical line at position x passes through a gap in a row if x is a gap position in that row. Gap positions are the prefix sums of brick widths within each row, excluding the total (wall edge).

Algorithm:

1. For each row, compute the prefix sum of brick widths (excluding the last brick). Each prefix sum is a gap position.
2. Count the frequency of each gap position across all rows using a hash map.
3. Find the maximum frequency max_gap in the map.
4. Return n - max_gap where n is the number of rows.

Why exclude the last brick? The problem says the line cannot pass through the edge of the wall. The wall edge is at sum(row) — the last cumulative sum. Including it would count the wall boundary as a gap, which is forbidden.

Edge case: If no gaps exist (every row is a single brick), the gap map is empty. max_gap = 0. Return n - 0 = n — the line must cross all n rows.

Visual Dry Run#

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

Total wall width = 6 (verify: 1+2+2+1=6, 3+1+2=6, etc.)

Gap positions per row (prefix sums, excluding total):

Gap frequency map:

Max frequency = 4 (at position 4).

Answer = 6 rows - 4 gap hits = 2 bricks crossed. Correct!

Solution (Optimal)#

from collections import defaultdict
 
def leastBricks(wall: list[list[int]]) -> int:
    # Map from gap position to count of rows with a gap there
    gap_count = defaultdict(int)
 
    for row in wall:
        pos = 0
        # Skip the last brick (wall edge — forbidden position)
        for brick in row[:-1]:
            pos += brick
            gap_count[pos] += 1
 
    # Most gaps hit = fewest bricks crossed
    max_gap = max(gap_count.values(), default=0)
    return len(wall) - max_gap

var leastBricks = function(wall) {
    // Map from gap position to frequency
    const gapCount = new Map();
 
    for (const row of wall) {
        let pos = 0;
        // Skip the last brick (wall edge is not a valid cut position)
        for (let i = 0; i < row.length - 1; i++) {
            pos += row[i];
            gapCount.set(pos, (gapCount.get(pos) || 0) + 1);
        }
    }
 
    // Find maximum gap frequency
    let maxGap = 0;
    for (const count of gapCount.values()) {
        maxGap = Math.max(maxGap, count);
    }
 
    return wall.length - maxGap;
};

Complexity Analysis

n * B is proportional to the total number of bricks across all rows, which is bounded by 2 * 10^4 per the constraint sum(wall[i].length) <= 2 * 10^4. So the algorithm is effectively O(total bricks) — linear in the input size.

Common Mistakes#

• Including the last brick in gap computation. row[:-1] in Python (or row.length - 1 in the loop bound in JavaScript) correctly skips the last brick. Including row[-1] adds the wall edge as a gap position, which is forbidden and inflates the gap count for the rightmost position.
• Not initializing max_gap = 0 for the case with no gaps. If every row is a single brick, gap_count is empty. max(empty, default=0) = 0 → return n - 0 = n. This is correct: the line must cross all n rows.
• Confusing prefix sum of bricks with individual brick positions. The gap is after the first brick at position brick_width, not at index 1. Always accumulate the sum.
• Treating the problem as finding the minimum per column. Some candidates iterate over each column (x-position) and count bricks in that column. This works but is O(n * W) — much slower than the gap map approach.
• Using a set instead of a map. A set tells you which positions have at least one gap but not how many gaps exist there. You need a frequency count to find the position with the most gaps.

Follow-up Questions#

What if the wall has non-integer (fractional) brick widths? The algorithm still works — use floating-point or fraction arithmetic for prefix sums. The hash map handles floating-point keys (though floating-point equality comparison can be tricky; use exact fractions or a tolerance-based approach).

What if the line must align with a grid (quantized positions)? Only check positions at integer multiples of the grid unit. No other change needed.

What if the problem asks for the minimum number of bricks that would need to be removed to allow a complete gap? For each position, count the number of rows where the position is NOT a gap. The minimum over all positions is the answer.

How would you find all optimal cut positions (not just the minimum count)? Collect all positions with frequency max_gap. Return all of them as valid answers.

What if rows have different heights (varying row heights)? Weight each row's gap positions by the row's height. The total crossings at position x is the sum of heights of rows where x is not a gap. Minimize over all x.

Key Takeaways#

• LC 554 Brick Wall flips the question: instead of minimizing crossings, MAXIMIZE the count of edges at a single position.
• For each row, compute prefix sums of brick widths EXCLUDING the rightmost edge — those are the internal gap positions.
• Increment a hashmap counter for each gap position; the answer is numRows - max(map.values()).
• Skip the right edge of every row (full-row prefix) — that boundary is the wall edge, not a brick gap.
• Time and space are O(total bricks) — single pass over all rows.
• An empty map (no internal gaps) means every row must be crossed; answer is numRows.
• This frequency-of-event-position pattern recurs in interval overlap problems (LC 253, LC 1094, LC 2251).

Related Problems#

• LC 554 — Brick Wall: This problem.
• LC 56 — Merge Intervals: Find the maximum overlap point in a set of intervals — similar frequency counting.
• LC 57 — Insert Interval: Interval manipulation — related gap-finding thinking.
• LC 1094 — Car Pooling: Difference array for tracking capacity across positions — same "count at each position" paradigm.
• LC 253 — Meeting Rooms II (Premium): Find minimum rooms needed — count overlapping intervals at each time point.
• LC 2251 — Number of Flowers in Full Bloom: Count active intervals at each query point — same frequency map pattern.