Course4all

Brick Wall

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Arrays & Hashing.

Brick Wall

There is a rectangular brick wall in front of you. The wall is n rows high and the width is the same for each row. You want to draw a vertical line from the top to the bottom and cross the least number of bricks. Each row is represented by a list of brick widths. A line crosses a brick if it passes through its interior, but not its edge.

Visual Representation

Row 1: [1, 2, 2, 1] -> Edges at: 1, 3, 5 Row 2: [3, 1, 2] -> Edges at: 3, 4 Frequency of Edges: 1: 1 3: 2 (Max! Draw line here) 5: 1 4: 1 Min bricks crossed = Total Rows - Max Edge Frequency
Medium

Examples

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

Level I: Brute Force

Intuition

Check every possible vertical line position (at every 0.5 unit width up to total width). For each position, count how many bricks are crossed. Extremely slow.
⏱ O(N * Width)💾 O(1)

Detailed Dry Run

Width=6. Check 1, 2, 3, 4, 5. Line at 3: Row1 (edge), Row2 (edge)... Crosses 0 bricks in those rows.
java
class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        int width = 0; for(int b : wall.get(0)) width += b;
        int minBricks = wall.size();
        for(int pos=1; pos<width; pos++) {
            int crossed = 0;
            for(List<Integer> row : wall) {
                int edge = 0; boolean onEdge = false;
                for(int b : row) {
                    edge += b; if(edge == pos) { onEdge = true; break; }
                    if(edge > pos) break;
                }
                if(!onEdge) crossed++;
            }
            minBricks = Math.min(minBricks, crossed);
        }
        return minBricks;
    }
}
Approach 2

Level II: HashMap (Edge Frequency)

Intuition

A line crosses the least bricks if it passes through the most edges. We use a HashMap to count the frequency of edges (prefix sums) at each position (excluding the far right edge).
⏱ O(N) where N is the total number of bricks.💾 O(M) where M is the number of unique edge positions.

Detailed Dry Run

Row: [1, 2, 2, 1] -> Edges: {1:1, 3:1, 5:1} Row: [3, 1, 2] -> Edges: {1:1, 3:2, 5:1, 4:1} Max edges = 2 (at pos 3). Min bricks = Rows(2) - Max(2) = 0.
java
class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        Map<Integer, Integer> counts = new HashMap<>();
        int maxEdges = 0;
        for (List<Integer> row : wall) {
            int edge = 0;
            for (int i = 0; i < row.size() - 1; i++) {
                edge += row.get(i);
                counts.put(edge, counts.getOrDefault(edge, 0) + 1);
                maxEdges = Math.max(maxEdges, counts.get(edge));
            }
        }
        return wall.size() - maxEdges;
    }
}
Approach 3

Level III: Optimal Solution (Pointer-based Merge)

Intuition

Similar to merging K sorted lists, we can treat each row's edges as a sorted list. Use pointers to advance through edges across all rows, counting occurrences at each position. This is more efficient if the number of bricks is massive but rows are few.
⏱ O(N log R) where N is total bricks and R is number of rows.💾 O(R) for pointers.

Detailed Dry Run

Row 1: [1, 2, 2, 1] -> Edges: [1, 3, 5] Row 2: [3, 1, 2] -> Edges: [3, 4] Initially: ptrs=[0, 0]. Curr Edges: [1, 3]. Min is 1. Pop 1. Next min is 3. Pop 3 from both. Count=2.
java
class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < wall.size(); i++) {
            if (wall.get(i).size() > 1) pq.offer(new int[]{wall.get(i).get(0), i, 0});
        }
        int maxEdges = 0;
        while (!pq.isEmpty()) {
            int currPos = pq.peek()[0];
            int count = 0;
            while (!pq.isEmpty() && pq.peek()[0] == currPos) {
                int[] top = pq.poll();
                count++;
                int rowIdx = top[1], brickIdx = top[2];
                if (brickIdx + 1 < wall.get(rowIdx).size() - 1) {
                    pq.offer(new int[]{currPos + wall.get(rowIdx).get(brickIdx + 1), rowIdx, brickIdx + 1});
                }
            }
            maxEdges = Math.max(maxEdges, count);
        }
        return wall.size() - maxEdges;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionEncode and Decode Strings
Next Question →Isomorphic Strings