Brick Wall

MediumArrays & Hashinghashing

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A rectangular brick wall has several rows. wall[i] lists the widths of the bricks in row i from left to right, and every row has the same total width. You want to draw one vertical line from top to bottom. The line crosses a brick unless it passes exactly along an edge between two bricks in that row. The line may **not** be drawn along the wall's left or right outer edge. Return the minimum number of bricks the line must cross. If no row has an interior edge (for example, every row is a single brick), the line crosses every row, so the answer is the number of rows.

Examples

Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
Output: 2
A line at x = 4 passes along brick edges in four of the six rows.
Input: wall = [[1],[1],[1]]
Output: 3
Each row is a single brick, so any line crosses all three.

Constraints

  • n == wall.length, 1 <= n <= 10^4
  • 1 <= wall[i].length <= 10^4
  • 1 <= wall[i][j] <= 2^31 - 1
  • Every row has the same total width, and the total number of bricks is at most 2 * 10^4

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More hashing problems