Problem Description
You are given a rectangular brick wall represented by a 2D array where each row contains the widths of bricks. A vertical line is to be drawn from the top to the bottom of the wall, and the goal is to minimize the number of bricks that are crossed by this line. If the line goes through the edge of a brick, that brick is not considered crossed.
Key Insights
- A vertical line can only be drawn between the bricks.
- The position of the vertical line matters; it should ideally be placed where the maximum number of edges of bricks align.
- By counting the edges of the bricks across all rows, we can determine how many bricks would be crossed at each possible position of the vertical line.
- The minimum number of crossed bricks will be equal to the total number of bricks minus the maximum number of edges that can be aligned.
Space and Time Complexity
Time Complexity: O(n * m), where n is the number of rows and m is the average number of bricks in a row. Space Complexity: O(k), where k is the number of unique positions for the edges (at most m).
Solution
To solve the problem, we can use a hash map (or dictionary) to keep track of how many times each edge position occurs across all rows. For each row, we calculate the cumulative width of the bricks to find the edges. After processing all rows, we will find the maximum count of aligned edges. The minimum crossed bricks will then be the total number of rows minus this maximum count.