Brick Wall
Explanation & Solution
Description
There is a rectangular brick wall in front of you. The wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in that row from left to right.
You need to draw a vertical line from the top to the bottom of the wall, crossing the fewest bricks as possible. If your line goes through the edge between two bricks, that brick is not considered crossed.
Return the minimum number of bricks the line must cross.
You cannot draw a line along the two vertical edges of the wall, so you must cross at least one layer of bricks.
Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
Output: 2
Explanation: Drawing a vertical line at position 4 from the left crosses only 2 bricks. Multiple rows have an edge at position 4.
Constraints
1 <= wall.length <= 10^41 <= wall[i].length <= 10^41 <= wall[i][j] <= 2^31 - 1- The sum of brick widths in each row is the same
Approach
Hash Maps pattern
1. Track Edge Positions
- For each row, compute the cumulative position of each edge between bricks
- Use a hash map to count how many rows have an edge at each position
- Do not count the rightmost edge (the wall boundary)
2. Compute Prefix Sums Per Row
- Iterate through each brick in a row, adding its width to a running
position - After adding each brick (except the last), record the edge position in the map
- Increment the count for that position
3. Find the Maximum Edge Count
- Track the maximum count across all edge positions
- The position with the most edges is the optimal line position
- Drawing a line there avoids crossing the most bricks
4. Calculate the Result
- The minimum bricks crossed =
wall.length - maxEdges - Total rows minus the rows where the line passes through an edge
- If no edges align (e.g., all single-brick rows), the result equals the number of rows
Key Insight
- Instead of counting bricks crossed, count edges aligned at each position and pick the maximum
- The answer is
total rows - max aligned edges