Brick Wall
Medium · hash map
A wall is built from several rows of bricks. Every brick is one unit tall, but bricks have different widths, and every row has the same total width. wall[i] lists the widths of the bricks in row i, from left to right.
You want to draw a straight vertical line from the top of the wall to the bottom. The line may run along the gap between two bricks (where one brick ends and the next begins), but it must not run along the left or right edge of the wall. If the line passes through the inside of a brick, that brick is crossed.
Return the smallest possible number of bricks the line crosses. If no gap lies strictly inside the wall, the line crosses one brick in every row, so return the number of rows.
Examples
Example 1
Input: wall = [[2, 3, 1], [1, 5], [4, 2], [2, 1, 3]]
Output: 2
Every row is 6 wide. The gap 2 units from the left lies in rows 1 and 4, so the line there crosses a brick in each of the other two rows.
Example 2
Input: wall = [[4], [4], [4]]
Output: 3
There is no gap inside the wall, so the line crosses all three bricks.
Constraints
- 1 <= len(wall) <= 10^4
- 1 <= len(wall[i])
- The total number of bricks in the wall is at most 2 * 10^4.
- 1 <= wall[i][j] <= 2^31 - 1
- Every row has the same total width, and that width is at most 2^31 - 1.