Cut Through the Fewest Bricks

Medium

A brick wall is made of horizontal rows of equal height. Row rows[i] lists the widths of its bricks from left to right; every row has the same total width. You must cut the wall with a single vertical line from top to bottom. Where the line runs along a seam between two bricks, that row is left intact; otherwise the brick it passes through gets cut. Cutting along the left or right edge of the wall is not allowed. Return the smallest number of bricks that have to be cut.

Example 1

rows=[[2, 3, 1], [4, 2], [2, 2, 2], [1, 1, 4]] → 1

Mark 2 is a seam in rows 0, 2 and 3. A cut there goes only through the brick of width 4 in row 1.

Example 2

rows=[[5], [5]] → 2

Each row is one brick across the whole width with no inner seams, so any cut goes through both.

Example 3

rows=[[3, 3], [3, 1, 2], [1, 2, 3]] → 0

Mark 3 is a seam in all three rows, so a cut there touches no bricks at all.

Constraints

1 ≤ len(rows) ≤ 10⁴
1 ≤ len(rows[i]) ≤ 10⁴
At most 5·10⁴ bricks in total
1 ≤ rows[i][j] ≤ 2³¹ − 1
Every row has the same total width

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table

Similar problems

Sudoku Board Without Clashes Medium Anagram Buckets Medium Zero Out the Crosses Medium Tree From Pre-Order and In-Order Walks Medium Tree From In-Order and Post-Order Walks Medium

Input

rows=[[2, 3, 1], [4, 2], [2, 2, 2], [1, 1, 4]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 42 tests on the server, hidden ones included.