Brick Wall
Medium · Arrays & Hashing · Array · Hash Table
Problem
A rectangular brick wall has n rows. Row i is given as wall[i], the widths of its bricks from left to right. Every row has the same total width, and every brick is one unit tall.
You draw one vertical line from the top of the wall to the bottom. The line crosses a brick unless it runs exactly along the edge between two bricks. You may not draw the line along the left or right outer edge of the wall.
Return the smallest number of bricks the line can cross.
Examples
Input: wall = [[2,1,3],[3,3],[1,2,3],[4,2]] Output: 1
A line at x = 3 runs along an edge in the first three rows and crosses only the 4-wide brick in the last row.
Input: wall = [[4],[4],[4]] Output: 3
Each row is a single brick, so any line inside the wall crosses all three.
Constraints
- n == len(wall)
- 1 <= n <= 10^4
- 1 <= len(wall[i]) <= 10^4
- 1 <= total number of bricks <= 2 · 10^4
- every row has the same total width, at most 2^31 - 1
- 1 <= wall[i][j] <= 2^31 - 1
Approaches
- Try every edge position against every row — time O(B²), space O(B)
Follow-up
What if the wall is streamed one row at a time and you must report the answer after each row? The hash map already supports it: keep the running best count, and the answer after r rows is r - best.
Related problems
Start free on Cariara · Coding problems · System design studio
