413. Brick Wall
You are standing in front of a rectangular brick wall built from n rows. Row i is given as a list wall[i] of positive brick widths laid left to right; every row adds up to the same total width, but the bricks inside each row can be sliced differently. All bricks are one unit tall.
You want to draw one straight vertical line from the top of the wall to the bottom that cuts through as few bricks as possible. A line that runs exactly along the seam between two neighboring bricks does not cut either of them — but drawing the line along the wall's left or right border is not allowed.
Your function receives wall, a list of rows where each row is a list of brick widths, and returns a single integer: the minimum number of bricks the line has to cut through.
Example 1:
Input: wall = [[2,1,3],[1,2,3],[3,3],[2,4]]
Output: 1
Explanation: The seam at distance 3 from the left border exists in rows 1, 2, and 3, so a line there slips between bricks in those rows and only cuts the last row's 4-wide brick.
Example 2:
Input: wall = [[3],[3],[3]]
Output: 3
Explanation: Every row is one solid brick, so there are no interior seams at all. Any allowed line cuts all 3 bricks.
Constraints:
- 1 ≤ n == wall.length ≤ 10⁴
- 1 ≤ wall[i].length ≤ 10⁴
- The total number of bricks is at most 2 * 10⁴.
- 1 ≤ wall[i][j] ≤ 2³¹ - 1
- Every row sums to the same width, which is at most 2³¹ - 1.
Hints:
The line avoids a brick only when it passes through a seam — and a seam in a row can only sit at a prefix sum of that row's widths (excluding the full width, which is the forbidden right border).
If some interior x-position has a seam in c of the n rows, a line there cuts exactly n − c bricks. So find the x-position shared by the most rows: count every row's interior prefix sums in one hash map and take the biggest count.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: wall = [[2,1,3],[1,2,3],[3,3],[2,4]]
Expected output: 1