Brick Wall

Problem Statement

You are given a rectangular brick wall with n rows. Each row consists of several bricks that can vary in width but have a uniform height of one unit. Every row aligns precisely with the others in terms of total width. You are to draw a vertical line from the top of the wall to the bottom which intersects the fewest number of bricks. A line passing through a brick's boundary (but not its body) does not count as intersecting the brick. A line cannot be drawn along the outer edges of the wall as it would bypass all bricks.

You need to determine the position where the line should be drawn such that it crosses the fewest bricks. The input is provided as a 2D array wall, where each sublist denotes a row of bricks represented by their widths. The goal is to find and return the minimum number of bricks that would be crossed by such a line.

Examples

Example 1

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

Input:

wall = [[1],[1],[1]]

Output:

3

Constraints

• n == wall.length
• 1 <= n <= 104
• 1 <= wall[i].length <= 104
• 1 <= sum(wall[i].length) <= 2 * 104
• sum(wall[i]) is the same for each row i.
• 1 <= wall[i][j] <= 231 - 1

Approach and Intuition

The fundamental intuition behind solving this problem lies in finding the most common edge across all rows of bricks, except the last boundary, which if used, would result in zero bricks being crossed. Here's a breakdown of the approach:

1. Calculate the cumulative width at each separator between bricks within each row and record these cumulative widths in a hash map (excluding the boundary after the last brick in any row).

2. For each row, add to the count of each edge's position in the hash map, excluding the last edge of the row.

3. After processing every row, determine the highest frequency of any particular edge position from the hash map. This frequency represents the most common place where a line could pass through and not intersect a brick.

4. Subtract this highest frequency from the total number of rows (n) to get the minimum number of bricks that would be crossed. This calculation stems from the fact that height of the line drawing—i.e., the number of layers or rows—is fixed, and reducing the crossings is achieved by identifying the most common 'gaps' or edges between bricks.

By applying this method, we strategically draw the line where there are the most common alignments of brick edges throughout the wall, minimizing the number of bricks intersected.

Solutions

public class Solution {
    public int minimumBricks(List<List<Integer>> wall) {
        HashMap<Integer, Integer> gaps = new HashMap<>();
        for (List<Integer> level : wall) {
            int position = 0;
            for (int j = 0; j < level.size() - 1; j++) {
                position += level.get(j);
                gaps.put(position, gaps.getOrDefault(position, 0) + 1);
            }
        }
        int minCross = wall.size();
        for (int gap : gaps.values())
            minCross = Math.min(minCross, wall.size() - gap);
        return minCross;
    }
}