Problem Description

The Brick Wall problem asks you to find the minimum number of bricks that a vertical line crosses when drawn from the top to the bottom of a brick wall. The wall is represented as a list of rows, where each row is a list of integers indicating the widths of bricks in that row. All rows are the same total width. You may draw the line anywhere between the bricks, but you cannot draw it along the two vertical edges of the wall (i.e., not at position 0 or the wall's rightmost edge).

Your task is to return the minimum number of bricks that the line crosses.

• Input: wall – a list of lists of integers, where each sublist represents a row of bricks.
• Output: An integer, the minimum number of bricks the vertical line crosses.
• Constraints: The line must go from the top to the bottom of the wall, and cannot coincide with the wall's edges.

Thought Process

At first glance, you might think you need to try every possible position for the vertical line and count how many bricks it crosses at each position. However, this would be inefficient, especially for large walls.

Instead, let's think about the problem differently: wherever the line passes through a gap between bricks (i.e., along the edge between two bricks), it does not cross a brick in that row. So, to minimize the number of bricks crossed, we want to draw the line along the position where the most rows have a brick edge (i.e., the most aligned gaps).

In other words, the answer is: the total number of rows minus the maximum number of aligned edges (gaps between bricks) at any position (excluding the wall's edges).

Solution Approach

Let's break down the optimized solution step by step:

1. Count the brick edge positions:
   • For each row, compute the prefix sums of brick widths, but exclude the last brick (since the rightmost edge is not allowed).
   • For every prefix sum (edge position), keep a count in a hash map (dictionary) of how many rows have a brick edge at that position.
2. Find the most common edge position:
   • The position where the most edges align is where the vertical line would cross the fewest bricks.
   • If no edges align (i.e., all rows are single bricks), the line must cross every row.
3. Compute the answer:
   • Subtract the maximum count of aligned edges from the total number of rows.

We use a hash map because it allows us to count edge positions efficiently in O(1) time per insert.

Example Walkthrough

Let's consider the following wall:

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

Step by step:

• For each row, calculate the prefix sums (excluding the last brick):
  • Row 1: 1, 3, 5
  • Row 2: 3, 4
  • Row 3: 1, 4
  • Row 4: 2
  • Row 5: 3, 4
  • Row 6: 1, 4, 5
• Count the occurrences of each edge position:
  • 1: 3 times
  • 2: 1 time
  • 3: 3 times
  • 4: 4 times
  • 5: 2 times
• The maximum aligned edge is at position 4 (occurs 4 times).
• The minimum number of bricks crossed is number of rows - 4 = 6 - 4 = 2.

Time and Space Complexity

• Brute-force approach:
  • For every possible position (up to the total width), check every row to see if the line crosses a brick. This is O(W * N), where W is the wall width and N is the number of rows.
• Optimized approach:
  • We process every brick in every row once, except the last brick, for a total of O(M), where M is the total number of bricks.
  • Hash map storage for edge counts is O(M).
• Summary: Time: O(M), Space: O(M)

Summary

The key insight for the Brick Wall problem is to focus on the positions between bricks (the edges) rather than the bricks themselves. By counting how many rows align at each edge position, we can efficiently determine the optimal place to draw the vertical line so that it crosses the fewest bricks. This approach is both elegant and efficient, using a hash map for fast counting and avoiding unnecessary brute-force checks.

Code Implementation

class Solution:
    def leastBricks(self, wall):
        from collections import defaultdict
        edge_count = defaultdict(int)
        for row in wall:
            position = 0
            # Exclude last brick to avoid counting the right edge
            for brick in row[:-1]:
                position += brick
                edge_count[position] += 1
        # If edge_count is empty, return number of rows
        max_edges = max(edge_count.values(), default=0)
        return len(wall) - max_edges
      

class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        unordered_map<int, int> edgeCount;
        for (const auto& row : wall) {
            int position = 0;
            for (int i = 0; i < row.size() - 1; ++i) {
                position += row[i];
                edgeCount[position]++;
            }
        }
        int maxEdges = 0;
        for (const auto& entry : edgeCount) {
            maxEdges = max(maxEdges, entry.second);
        }
        return wall.size() - maxEdges;
    }
};
      

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        Map<Integer, Integer> edgeCount = new HashMap<>();
        for (List<Integer> row : wall) {
            int position = 0;
            for (int i = 0; i < row.size() - 1; i++) {
                position += row.get(i);
                edgeCount.put(position, edgeCount.getOrDefault(position, 0) + 1);
            }
        }
        int maxEdges = 0;
        for (int count : edgeCount.values()) {
            maxEdges = Math.max(maxEdges, count);
        }
        return wall.size() - maxEdges;
    }
}
      

var leastBricks = function(wall) {
    const edgeCount = new Map();
    for (const row of wall) {
        let position = 0;
        for (let i = 0; i < row.length - 1; i++) {
            position += row[i];
            edgeCount.set(position, (edgeCount.get(position) || 0) + 1);
        }
    }
    let maxEdges = 0;
    for (const count of edgeCount.values()) {
        if (count > maxEdges) maxEdges = count;
    }
    return wall.length - maxEdges;
};