Brick Wall [Medium] — Gap Position Frequency Map

Problem Statement

A brick wall is represented as rows of bricks. Draw a vertical line so it crosses the minimum number of bricks (not at edges). Return that minimum count.

Input: [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
Output: 2

Intuition

Count frequency of each gap position across all rows. The vertical line at the most frequent gap position crosses the fewest bricks. min_bricks = total_rows - max_gap_count.

Solutions

Python

from collections import defaultdict

def leastBricks(wall: list[list[int]]) -> int:
    gaps = defaultdict(int)
    for row in wall:
        pos = 0
        for brick in row[:-1]:  # skip last (wall edge)
            pos += brick
            gaps[pos] += 1
    max_gap = max(gaps.values(), default=0)
    return len(wall) - max_gap

C++

int leastBricks(vector<vector<int>>& wall) {
    unordered_map<int,int> gaps;
    for(auto& row:wall){int pos=0;for(int i=0;i<row.size()-1;i++){pos+=row[i];gaps[pos]++;}}
    int maxGap=0;
    for(auto& [k,v]:gaps) maxGap=max(maxGap,v);
    return wall.size()-maxGap;
}

Java

public int leastBricks(List<List<Integer>> wall) {
    Map<Integer,Integer> gaps=new HashMap<>();
    for(List<Integer> row:wall){
        int pos=0;
        for(int i=0;i<row.size()-1;i++){pos+=row.get(i);gaps.merge(pos,1,Integer::sum);}
    }
    int max=0; for(int v:gaps.values()) max=Math.max(max,v);
    return wall.size()-max;
}

Complexity

Time: O(n×m) n=rows, m=avg bricks/row
Space: O(width)