Show problems as
Classic problem #554MediumArrayHash Table

Brick Wall

Real-world version: Cable Drop Through The Panel Partition
Tracked in this browser only
Read Brick Wall on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

An office partition is described by wall, listed from the top row downwards. Row i is the list of panel widths in that row, read from the left edge to the right edge, and every row spans the same total width.

A cable is dropped straight down the partition, from the top of the top row to the bottom of the bottom row, at one position strictly inside the partition: the two outer edges are not allowed. In each row the cable either slips down the seam where two neighbouring panels meet, touching neither of them, or it passes through the body of one panel. Return the smallest number of panels a single cable can pass through.

Examples

Example 1

Input
wall = [[4, 4], [2, 6], [2, 6], [3, 5]]
Output
2

Every row is 8 wide. A cable dropped 2 from the left edge slips down the seam of row 1 and the seam of row 2, and passes through a panel in row 0 and in row 3, giving 2 panels.

Example 2

Input
wall = [[1, 1, 1], [3], [1, 2]]
Output
1

Every row is 3 wide. A cable dropped 1 from the left edge slips down a seam in row 0 and a seam in row 2, and passes through the single panel of row 1, giving 1 panel.

Example 3

Input
wall = [[6], [6], [6]]
Output
3

Each row holds one panel 6 wide and has no seam, and the cable is not allowed on either outer edge, so it passes through a panel in all 3 rows.

Constraints

  • n == wall.length
  • 1 <= n <= 10^4
  • 1 <= wall[i].length <= 10^4
  • 1 <= sum of all wall[i].length <= 2 * 10^4
  • Every row of wall has the same total width.
  • 1 <= wall[i][j] <= 2^31 - 1

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def least_bricks(wall: list[list[int]]) -> int:
Java
public int leastBricks(List<List<Integer>> wall)

More on the same topics