Brick Wall
mediumTime: O(n)Space: O(n)
Recognize the pattern
find minimum bricks crossed by vertical linemaximize gaps alignedcount gap positions
Brute force idea
Try every possible x-position — O(n × width).
Better approach
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).
Key invariant
A vertical line crosses a brick unless it passes through a gap. Maximizing gaps aligned at the same x-position minimizes bricks crossed.
Watch out for
Counting bricks instead of gaps — count gaps, then bricks crossed = total rows - max gaps at any x.