Back to solutions

Brick Wall

MediumArrays

Draw a vertical line crossing the fewest bricks.

Open problem
Constraints
  • 1 <= r <= 10^4
  • All rows share the same total width

Count shared edges

Time O(total bricks)Space O(total edges)

A vertical line crosses a brick unless it falls on that brick's right edge. So crossing the fewest bricks means passing through the most shared internal edges. For each row, compute the running positions of internal brick boundaries and count how often each boundary occurs across rows. The answer is rows minus the most popular boundary count.

Key terms
internal edge:
A boundary between two bricks in a row, excluding the far left and right walls.
most common boundary:
The vertical position where the greatest number of rows have an edge.
int leastBricks(vector<vector<int>>& wall) {
    unordered_map<long long, int> edges; int best = 0;
    for (auto& row : wall) {
        long long pos = 0;
        for (size_t i = 0; i + 1 < row.size(); i++) {
            pos += row[i];
            best = max(best, ++edges[pos]);
        }
    }
    return (int)wall.size() - best;
}
Step by step
  1. For each row, accumulate prefix widths to get internal boundary positions (skip the last edge).
  2. Tally how many rows have a boundary at each position.
  3. Find the position shared by the most rows.
  4. The minimum crossings is the number of rows minus that maximum.