Course4all
Join us on telegram
Home/dsa/Arrays & Hashing/Brick Wall

Brick Wall

Master this topic with zero to advance depth.

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;
    }
}
← Previous QuestionEncode and Decode Strings
Next Question →Isomorphic Strings