318. Brick Wall
Problem
A rectangular wall consists of rows of bricks. Every row has the same total width, but brick widths may differ. Draw one vertical line from top to bottom so that it crosses the fewest bricks. The line may pass through brick boundaries but cannot be drawn along either outer edge. Return the minimum number of crossed bricks.
Examples
Example 1
Input: [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
Output: 2
Example 2
Input: [[1],[1],[1]]
Output: 3
Example 3
Input: [[1,1],[2],[1,1]]
Output: 1
Constraints
� 1 <= wall.length <= 10000
� 1 <= wall[i].length <= 10000
� The sum of brick widths is equal for every row.
Hints
?? Instead of counting bricks crossed, count aligned internal edges.
?? Compute prefix positions for every row except the final outer boundary.
?? The best line passes through the most frequently occurring internal edge.
Expected Complexity
Follow-up
Why must the final prefix sum of each row be excluded?
Practice Notes
Attempts: 0
Time spent: 0min
Hints used: 0
[[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]Expected
2