Fewest Bricks Crossed
MediumArrays & Hashing
Problem
An electrician must run a vertical cable from the top of a brick wall to the bottom. The wall has several rows; wall[r] lists the widths of the bricks in row r from left to right, and every row has the same total width.
The cable may pass through the seam between two bricks for free, but every brick it passes through must be drilled. The cable cannot run along the wall's left or right edge. Return the minimum number of bricks that must be drilled.
Example 1
- Input:
- wall = [[2, 1, 1], [1, 2, 1], [3, 1], [1, 1, 2]]
- Output:
- 1
At distance 3 from the left edge, rows 0, 1 and 2 have a seam; only row 3's last brick (spanning 2–4) is drilled.
Example 2
- Input:
- wall = [[1], [1], [1]]
- Output:
- 3
Each row is a single brick, so there are no inner seams.
Constraints
- 1 ≤ rows ≤ 10^4
- 1 ≤ wall[r].length ≤ 10^4
- Total bricks ≤ 2·10^5
- 1 ≤ brick width ≤ 2^31 - 1, and every row has the same sum.
Hint
Show the first hint
Instead of counting drilled bricks, count the rows where the cable passes through a seam.
Walkthrough
How to approach it
01Clarify before coding
- Can the cable run along the outer edges? No, so the full-width position is excluded.
- Can widths be huge? Yes, so positions must be stored in a hash map, not an array indexed by position.
- Is a row with a single brick possible? Yes; it has no inner seams.
02Brute force
Try every integer position from 1 to width - 1 and, for each, count the rows that do not have a seam there.
Cost: O(width · rows) time, and the width can be around 2^31: hopeless.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.