Brick Wall
mediumTime: O(n)Space: O(n)
Signals to notice
find minimum bricks crossed by vertical linemaximize gaps alignedcount gap positions
Brute force first
Try every possible x-position — O(n × width).
The key insight
For each row, compute prefix sums (gap positions). Count gaps at each x-position using a hash map. The x with the most gaps crosses the fewest bricks. Answer = rows - maxGaps. O(total bricks).
What must stay true
A vertical line crosses a brick unless it passes through a gap. Maximizing gaps aligned at the same x-position minimizes bricks crossed.
Easy way to go wrong
Counting bricks instead of gaps — count gaps, then bricks crossed = total rows - max gaps at any x.