Problem

There is a rectangular brick wall in front of you with n rows of bricks. The ith row has some number of bricks each of the same height (i.e., one unit) but they can be of different widths. The total width of each row is the same.

Draw a vertical line from the top to the bottom and cross the least bricks. If your line goes through the edge of a brick, then the brick is not considered as crossed. You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.

Given the 2D array wall that contains the information about the wall, return the minimum number of crossed bricks after drawing such a vertical line.

Examples

Example 1:

1
2
3
4

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:

1
2
3
4

Input:
wall = [[1],[1],[1]]
Output:
 3

Solution

Method 1 – Hash Map for Edge Counting

Intuition

The main idea is to find a vertical line that passes through the maximum number of brick edges (gaps) between bricks, so it crosses the fewest bricks. For each row, we compute the prefix sum of brick widths to find the positions of the gaps (excluding the last edge, which is the wall’s end). We use a hash map to count how many times each gap position occurs. The optimal line is drawn at the gap position with the highest count, so the minimum number of crossed bricks is number of rows - max gap count.

Approach

  1. Initialize a hash map to count the frequency of each gap position (prefix sum of brick widths, excluding the last brick in each row).
  2. For each row, compute the prefix sum for each brick except the last, and update the hash map.
  3. Track the maximum frequency of any gap position (max_gap_count).
  4. The answer is number of rows - max_gap_count.
  5. Handle edge cases: if no gap exists (all rows have one brick), the line must cross all bricks.

Complexity

  • ⏰ Time complexity: O(N), where N is the total number of bricks in the wall, since we process each brick once.
  • 🧺 Space complexity: O(M), where M is the number of unique gap positions, as we store them in a hash map.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        unordered_map<int, int> gaps;
        int max_gap = 0;
        for (const auto& row : wall) {
            int sum = 0;
            for (int i = 0; i < row.size() - 1; ++i) {
                sum += row[i];
                gaps[sum]++;
                max_gap = max(max_gap, gaps[sum]);
            }
        }
        return wall.size() - max_gap;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func leastBricks(wall [][]int) int {
    gaps := make(map[int]int)
    maxGap := 0
    for _, row := range wall {
        sum := 0
        for i := 0; i < len(row)-1; i++ {
            sum += row[i]
            gaps[sum]++
            if gaps[sum] > maxGap {
                maxGap = gaps[sum]
            }
        }
    }
    return len(wall) - maxGap
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public int leastBricks(List<List<Integer>> wall) {
    Map<Integer, Integer> map = new HashMap<>();
    int gapCount = 0;
    for (List<Integer> row : wall) {
        int sum = 0;
        for (int i = 0; i < row.size() - 1; i++) {
            sum += row.get(i);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
            gapCount = Math.max(gapCount, map.get(sum));
        }
    }
    return wall.size() - gapCount;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun leastBricks(wall: List<List<Int>>): Int {
        val gaps = mutableMapOf<Int, Int>()
        var maxGap = 0
        for (row in wall) {
            var sum = 0
            for (i in 0 until row.size - 1) {
                sum += row[i]
                gaps[sum] = gaps.getOrDefault(sum, 0) + 1
                maxGap = maxOf(maxGap, gaps[sum]!!)
            }
        }
        return wall.size - maxGap
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def leastBricks(wall: list[list[int]]) -> int:
    gaps: dict[int, int] = {}
    max_gap = 0
    for row in wall:
        s = 0
        for brick in row[:-1]:
            s += brick
            gaps[s] = gaps.get(s, 0) + 1
            max_gap = max(max_gap, gaps[s])
    return len(wall) - max_gap
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn least_bricks(wall: Vec<Vec<i32>>) -> i32 {
        use std::collections::HashMap;
        let mut gaps = HashMap::new();
        let mut max_gap = 0;
        for row in wall.iter() {
            let mut sum = 0;
            for &brick in &row[..row.len()-1] {
                sum += brick;
                let cnt = gaps.entry(sum).or_insert(0);
                *cnt += 1;
                if *cnt > max_gap {
                    max_gap = *cnt;
                }
            }
        }
        (wall.len() as i32) - max_gap
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    leastBricks(wall: number[][]): number {
        const gaps: Record<number, number> = {};
        let maxGap = 0;
        for (const row of wall) {
            let sum = 0;
            for (let i = 0; i < row.length - 1; i++) {
                sum += row[i];
                gaps[sum] = (gaps[sum] || 0) + 1;
                maxGap = Math.max(maxGap, gaps[sum]);
            }
        }
        return wall.length - maxGap;
    }
}