Brick Wall
There is a rectangular brick wall in front of you with n rows of bricks. The i^th row has some number of bricks, each of the same height (one unit), but the bricks can have different widths. The total width of each row is the same.
Draw a vertical line from the top to the bottom so that it crosses the fewest bricks. If your line goes through the edge of a brick, then that brick is not considered crossed. You cannot draw a line just along one of the two vertical edges of the wall, because in that case the line would obviously cross no bricks.
Given the 2D array wall that contains the information about the wall, return the minimum number of crossed bricks after drawing such a vertical line.
Example 1
Input
wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]Output
2A vertical line can be drawn through internal brick edges in four rows, so it crosses only 2 bricks.
Example 2
Input
wall = [[1],[1],[1]]Output
3There are no internal brick edges to use, so the line must cross all 3 bricks.
Constraints
- n == wall.length
- 1 <= n <= 10^4
- 1 <= wall[i].length <= 10^4
- 1 <= sum(wall[i].length) <= 2 * 10^4
- sum(wall[i]) is the same for each row i.
- 1 <= wall[i][j] <= 2^31 - 1