Brick Wall — Medium Problem & Solution

Problem statement

A rectangular brick wall is given as wall, where wall[i] lists the widths of the bricks in row i from left to right. Every row has the same total width.

Draw a vertical line from top to bottom. The line crosses a brick unless it falls exactly on that brick's edge. The line may not be drawn along either outer border.

Return the fewest bricks the line must cross.

Example 1

Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
Output: 2
Explanation: A line at offset 4 passes through the edges of four rows, so it crosses only the other two.

Example 2

Input: wall = [[1],[1],[1]]
Output: 3
Explanation: Only the outer borders are edges, and those are not allowed — every line crosses all three bricks.

Example 3

Input: wall = [[2,2],[2,2],[1,3]]
Output: 1
Explanation: A line at offset 2 falls on an edge in the first two rows, so it crosses only the third.

Constraints

• 1 <= wall.length <= 10000
• 1 <= wall[i].length <= 10000
• Each row sums to the same total width.
• 1 <= brick width <= 2147483647

How to solve Brick Wall

Flip the objective. A line at a given offset crosses rows - (number of rows whose edge falls there) bricks, so minimising crossings means maximising shared edges.

Approach

1. For every row, walk its bricks accumulating a running width and record each running total except the last, which is the wall's right border.
2. Tally these offsets in a hash map across all rows.
3. The answer is wall.length - maxTally.

Why it works

Each row contributes at most one edge at a given offset, so the tally at an offset is exactly the number of rows the line slips through. Excluding the final prefix sum is what enforces the rule against drawing along the outer border — and it also handles the all-one-brick case, where no offsets are recorded and the answer is every row.

Complexity

• Time — O(total bricks)
• Space — O(distinct offsets)

Pitfalls

• Including the last prefix sum makes the right border look like the best line and returns 0.
• Brick widths reach the 32-bit limit, so the running offset needs 64 bits in fixed-width languages.
• Scanning candidate offsets one by one is hopeless — the wall can be billions of units wide.

Reference solution

Python

from typing import List

def leastBricks(wall: List[List[int]]) -> int:
    edges = {}
    best = 0
    for row in wall:
        x = 0
        for w in row[:-1]:
            x += w
            edges[x] = edges.get(x, 0) + 1
            best = max(best, edges[x])
    return len(wall) - best

JavaScript

var leastBricks = function(wall) {
    var edges = {}, best = 0;
    for (var r = 0; r < wall.length; r++) {
        var row = wall[r], x = 0;
        for (var i = 0; i + 1 < row.length; i++) {
            x += row[i];
            var key = String(x);
            edges[key] = (edges[key] === undefined ? 0 : edges[key]) + 1;
            if (edges[key] > best) best = edges[key];
        }
    }
    return wall.length - best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Count Number of Texts Medium
• Construct String With Repeat Limit Medium
• Minimum Number of Steps to Make Two Strings Anagram II Medium
• Count Vowel Substrings of a String Medium
• Minimum Length of String After Operations Medium
• Sum of Digit Differences of All Pairs Medium