Back to DSA sheet
Brick Wall
MediumArraysA wall has rows of bricks of various widths; every row has the same total width. Draw a vertical line from top to bottom that is not at the far left or right edge, crossing as few bricks as possible. A line at a brick boundary does not cross that brick. Return the minimum number of bricks crossed.
Input format (stdin): the first line has r (rows). Each of the next r lines starts with the count of bricks in that row, followed by their widths. Output the minimum crossings.
Examples
Input: 6
4 1 2 2 1
3 3 1 2
3 1 3 2
4 2 4
5 3 1 2
6 1 1 1 1 2
Output: 3
The best vertical line crosses 3 bricks (6 rows minus the 3 sharing a common edge).
Constraints
- 1 <= r <= 10^4
- All rows share the same total width
Sheets
NeetCode 250
brick-wall.cpp2 sample tests
Loading editor
Test results
Run the sample tests to check your solution against expected output.
Custom input (stdin)
Output
Run your code to see its output.