Brick Wall

Medium
676.

Brick Wall

Brick Wall is a medium coding problem on arrays, hash table and counting, asked in Amazon, Google and Meta interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} wall
 * @return {number}
 */
var leastBricks = function(wall) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Brick Wall — Solution in Python, Java & C++

Brick Wall solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.

Brick Wall is a medium coding problem on arrays, hash table and counting, asked in Amazon, Google and Meta interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Counting
  • Asked at: Amazon, Google, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Brick Wall

  1. Hint 1

    Crossing the fewest bricks is the same as passing through the most edges.

  2. Hint 2

    For each row, the interior edges sit at its running prefix sums — excluding the final one, which is the outer border.

  3. Hint 3

    Tally those offsets across all rows; the busiest offset wins.

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

Java

public static int leastBricks(int[][] wall) {
    Map<Long, Integer> edges = new HashMap<>();
    int best = 0;
    for (int[] row : wall) {
        long x = 0;
        for (int i = 0; i + 1 < row.length; i++) {
            x += row[i];
            int c = edges.getOrDefault(x, 0) + 1;
            edges.put(x, c);
            if (c > best) best = c;
        }
    }
    return wall.length - best;
}

C++

int leastBricks(vector<vector<int>>& wall) {
    unordered_map<long long, int> edges;
    int best = 0;
    for (auto& row : wall) {
        long long x = 0;
        for (size_t i = 0; i + 1 < row.size(); i++) {
            x += row[i];
            int c = ++edges[x];
            if (c > best) best = c;
        }
    }
    return (int) wall.size() - 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets