NeetCode #107LC-554MediumArrays & Hashing
← Back to All Problems#107 · #554 · Brick Wall(砖墙)
📌 Problem Statement & Constraints
There is a rectangular brick wall made of rows of bricks of varying widths but the same height. Draw a vertical line from the top to the bottom that crosses the fewest bricks. Return that minimum number. The line must not run along an edge at either end of the wall. Constraints:
1 <= wall.length <= 10^4, 1 <= wall[i].length <= 10^4, 1 <= wall[i][j] <= 2^31 - 1.💡 Core Algorithmic Approaches
- A vertical line crosses the fewest bricks where the most brick edges align.
- For each row, record the cumulative width after each brick except the last -- the last edge is the right boundary, which is excluded by the problem statement.
- Count how many rows have an edge at each cumulative position.
- The answer is
number_of_rows - max(edge_count). If no interior edge exists anywhere, the line must cross every row, so the answer is the number of rows.
💻 Benchmark Python3 Implementation
class Solution:
def leastBricks(self, wall: List[List[int]]) -> int:
from collections import defaultdict
edges = defaultdict(int)
for row in wall:
pos = 0
for w in row[:-1]: # exclude the outer right edge
pos += w
edges[pos] += 1
if not edges:
return len(wall) # no interior edge -> must cross every row
return len(wall) - max(edges.values())⚡ Complexity Deep Dive
⏱️ Time Complexity
O(total bricks): one pass over the wall.
💾 Space Complexity
O(number of distinct edge positions).
⚠️ Interview Pitfalls & Follow-ups
- Including the final edge of each row: the right boundary of the wall is excluded by the problem, and including it would add every row to the same position, yielding a wrong answer of 0.
- Using the brick widths instead of cumulative positions: the line position is a cumulative width, not an individual brick width.
- Returning
max(edges.values()): that is the number of rows not crossed; the answer is the complement. - Handling a wall with a single brick per row: then there are no interior edges, and the answer is the number of rows.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.